Блог пользователя huajun

Автор huajun, история, 13 месяцев назад, По-английски

(I'm too lazy to write a post so I copied last year's, thanks feeder1 and pooty)

Hello, Codeforces community!

We are happy to invite you to participate in National University of Singapore (NUS) CS3233 Final Team Contest 2025 Mirror on 14.04.2025 12:15 (Московское время). CS3233 is a course offered by NUS to prepare students in competitive problem solving.

The contest is unofficial and will be held in Codeforces Gym. Standard ICPC rules (Unrated, ICPC Rules, Teams Preferred) apply. The contest is unrated. Note the unusual starting time.

The problems are written and prepared by user202729, rama_pang, feeder1, lovemathboy, tzaph_ and huajun.

We would also like to thank:

The contest will last for 5 hours and consist of 13 problems. While it is preferred to participate in a team, individual participation is also allowed.

The problems themselves may be quite standard as they are targeted toward those who have just learned competitive problem solving. However, we have also included a few challenging problems for stronger teams, such as ex-IOI or ICPC participants taking part in the course as well. So, the participants can expect a good mix of problems of varying difficulty levels, that we hope can be educational!

We hope you will enjoy and have fun in the contest. Good luck!

UPD: Thank you for your participation, sorry for the issues with the long queue. Editorial has been uploaded here

  • Проголосовать: нравится
  • +202
  • Проголосовать: не нравится

»
13 месяцев назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

Can I participate in the mirror instead :)

»
13 месяцев назад, скрыть # |
Rev. 5  
Проголосовать: нравится -8 Проголосовать: не нравится

baozii!!!

»
13 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

Please enable test data and detailed verdict: I still have no clues why my submission to E is incorrect (already made reasonable attempts of validating outputs).

Update: Thanks to communications from the problemsetters, my solution on E is incorrect because there is a (implied but not very clear) requirement of you cannot have well connected cycle of pipes but otherwise do not extract any oil. This gave a not-very-helpful message of "Unrecognized or misaligned character"

»
13 месяцев назад, скрыть # |
 
Проголосовать: нравится -6 Проголосовать: не нравится

Why my code for problem k: Kanto To Johto, giving TLE

#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
#define pb push_back

struct Compare{
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
        return a.second < b.second;
    }
};

struct Compare1{
    bool operator()(const ll a, const ll b) const {
        return a > b;
    }
};
bool compare(const vector<int>& a, const vector<int>& b) {
    return a[1] < b[1];
}

ll solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> edges;
    vector<vector<pair<int, int>>> adj(n, vector<pair<int, int>>());
    for(int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        x--;
        y--;
        adj[x].pb({y, w});
        adj[y].pb({x, w});
        edges.pb({x, y, w});
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq1;
    vector<ll> distArr(n, LONG_LONG_MAX);
    distArr[0] = 0;
    pq1.push({0, 0});
    while(!pq1.empty()){
        pair<int, int> delPair = pq1.top();
        pq1.pop();
        for(pair<int, int> x: adj[delPair.first]) {
            if(distArr[delPair.first] + x.second < distArr[x.first]){
                distArr[x.first] = distArr[delPair.first] + x.second;
                pq1.push({x.first, distArr[x.first]});
            }
        }
    }
    ll ans1 = distArr[n - 1];
    
    vector<ll> myArr1(m, LONG_LONG_MAX);
    for(int i = 0; i < m; i++) {
        if(distArr[edges[i][0]] != LONG_LONG_MAX) myArr1[i] = edges[i][2];
    }

    sort(myArr1.begin(), myArr1.end());

    ll ans = 0;
    for(int i = 0; i < k; i++) {
        if(myArr1[i] == LONG_LONG_MAX) break;
        ans += myArr1[i];
    }
    return min(ans, ans1);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while(t--)
    {
        ll x = solve();
        cout << x << "\n";
    }
    return 0;
}