Submission #1062193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062193		codexistent	Traffic (CEOI11_tra)	C++14	0 / 100	704 ms	78420 KiB

tra

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 300005
#define MAXM 900005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
#define f first
#define s second

ll n, m, c, MAXX, MAXY, p[MAXN], sz[MAXN], ct[MAXN];
pair<ll, ll> vp[MAXN];
vector<ll> adj[MAXN], radj[MAXN], ts;
bool vis[MAXN];
stack<ll> s;

ll find(ll x){
    return (p[x] == x) ? x : (p[x] = find(p[x])); 
}

void onion(ll a, ll b){
    a = find(a), b = find(b);
    if(a == b) return;

    if(sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    p[a] = p[b] = a;
}

void dfs1(ll v){
    if(vis[v]) return;
    vis[v] = true;

    for(ll v2 : adj[v]) dfs1(v2);
    s.push(v);
}

void dfs2(ll v){
    if(vis[v]) return;
    vis[v] = true;

    for(ll v2 : radj[v]) {
        v2 = find(v2);
        if(!vis[v2]) onion(v, v2);
        dfs2(v2);
    }
}

void dfs3(ll v){
    if(vis[v]) return;
    vis[v] = true;

    for(ll v2 : adj[v]){
        v2 = find(v2);
        dfs3(v2);
    }
    ts.push_back(v);
}

int main(){
    cin >> n >> m >> MAXX >> MAXY;
    FOR(i, 1, n) cin >> vp[i].f >> vp[i].s;
    FOR(i, 1, m) {
        ll a, b, ct; cin >> a >> b >> ct;
        adj[a].push_back(b), radj[b].push_back(a);
        if(ct == 2) adj[b].push_back(a), radj[a].push_back(b);
    }

    // cout << "END 1" << endl; 

    // Kosarju's
    FOR(i, 1, n) vis[i] = false;
    FOR(i, 1, n) dfs1(i);

    FOR(i, 1, n) vis[i] = false, p[i] = i, sz[i] = 1;
    while(!s.empty()){
        ll si = s.top(); s.pop();
        dfs2(si);
        //cout << "FIRST: " << si << endl;
    }

    /*FOR(i, 1, n){
        cout << "NODE " << i << " BELONGS IN GROUP OF " << find(i) << endl;
    }*/

    // Topological sort
    FOR(i, 1, n) vis[i] = false;
    FOR(i, 1, n) dfs3(find(i)), ct[i] = 0;

    //cout << "END 2" << endl; 

    FOR(i, 1, n) ct[find(i)] += (vp[i].f == MAXX), vis[i] = false;
    /*FOR(i, 1, n){
        cout << i << " HAS CT OF " << ct[find(i)] << endl;
    }*/
    for(ll i : ts){
        i = find(i);
        if(!vis[i]){
            vis[i] = true;
            ll adjn = 0;
            for(ll i2 : adj[i]) if(find(i2) != i) {
                i2 = find(i2);
                adjn++;
                ct[i] += ct[i2];
            }
        }
    }

    //cout << "END 3" << endl; 

    /*FOR(i, 1, n){
        cout << i << " HAS CT OF " << ct[find(i)] << endl;
    }*/

    set<pair<ll, ll>> st;
    FOR(i, 1, n){
        if(vp[i].f == 0) st.insert({vp[i].s, ct[find(i)]});
    }
    for(pair<ll, ll> i : st){
        cout << i.s << endl;
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 8
• Subtask 5: 0 / 8
• Subtask 6: 0 / 8
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9