oj.uz

Submission #1062193

# Submission time Handle Problem Language Result Execution time Memory
1062193 2024-08-16T21:04:37 Z codexistent Traffic (CEOI11_tra) C++14
0 / 100
 704 ms 78420 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20828 KB Output is correct
2 Incorrect 3 ms 20828 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 20828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 20828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 21084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 24772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 27476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 31096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 34900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 42580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 370 ms 52820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 704 ms 78420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 47444 KB Output isn't correct
2 Halted 0 ms 0 KB -