oj.uz

Submission #1066129

# Submission time Handle Problem Language Result Execution time Memory
1066129 2024-08-19T15:15:09 Z codexistent Traffic (CEOI11_tra) C++14
100 / 100
 989 ms 111852 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], en[MAXN], pfx[MAXN];
pair<ll, ll> vp[MAXN], rng[MAXN];
vector<ll> adj[MAXN], radj[MAXN], ts;
bool vis[MAXN], rw[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);
    }
 
 
    // 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);
    }
 
    // Topological sort
    FOR(i, 1, n) {
        if(find(i) != i){
            ll fi = find(i);
            for(ll i2 : adj[i]){
                adj[fi].push_back(i2);
            }
            for(ll i2 : radj[i]){
                radj[fi].push_back(i2);
            }
        }
    }
    FOR(i, 1, n) vis[i] = false;
    FOR(i, 1, n) dfs3(find(i));
 
    // sort east nodes by top to bottom y values
    vector<pair<ll, ll>> ev;
    FOR(i, 1, n) {
        if(vp[i].f == MAXX){
            ev.push_back({vp[i].s, i});
        }else{
            en[i] = -1;
        }
    }
    sort(begin(ev), end(ev));
 
    // first topological order run
    FOR(i, 1, n) rw[i] = false;
    FOR(i, 1, n) rw[find(i)] |= (vp[i].f == 0);
    for(ll i = ts.size() - 1; i >= 0; i--){
        ts[i] = find(ts[i]);
        //cout << "WE HAVE ORDER " << ts[i] << " WITH PRE'S ";
        for(ll i2 : radj[ts[i]]) {
            rw[ts[i]] |= rw[find(i2)];
            //cout << " " << find(i2) << "(" << i2 << ")";
        }
        //cout << endl;
    }
    /*FOR(i, 1, n){
        cout << "REACH WEST FOR " << i << " IS " << rw[i] << endl;
    }*/
 
    // final topological order run
    pfx[0] = 0;
    FOR(i, 0, ev.size() - 1) en[ev[i].s] = i + 1;
    FOR(i, 1, n) rng[find(i)] = {LONG_LONG_MAX, LONG_LONG_MIN};
    FOR(i, 1, n) {
        if(vp[i].f == MAXX && rw[find(i)]) {
            rng[find(i)].f = min(rng[find(i)].f, en[i]);
            rng[find(i)].s = max(rng[find(i)].s, en[i]);
        }
        vis[i] = false;
    }
    FOR(i, 1, ev.size()) pfx[i] = pfx[i - 1] + (rng[ev[i - 1].s].f != LONG_LONG_MAX);
 
    for(ll i : ts){
        i = find(i);
        if(!vis[i]){
            vis[i] = true;
            for(ll i2 : adj[i]) if(find(i2) != i) {
                i2 = find(i2);
 
                rng[i].f = min(rng[i].f, rng[i2].f);
                rng[i].s = max(rng[i].s, rng[i2].s);
            }
        }
    }
 
    /*FOR(i, 1, n){
        cout << "NODE " << i << " HAS RANGE " << rng[i].f << " to " << rng[i].s << endl; 
    }*/
 
    set<pair<ll, ll>> st;
    FOR(i, 1, n){
        if(vp[i].f == 0) st.insert({-vp[i].s, find(i)});
    }
    for(pair<ll, ll> i : st){
        if(rng[i.s].f == LONG_LONG_MAX){
            cout << 0 << endl;
        }else{
            cout << (pfx[rng[i.s].s] - pfx[rng[i.s].f - 1]) << endl;
        }
    }
}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:6:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i, a, b) for(ll i = a; i <= b; i++)
......
  123 |     FOR(i, 0, ev.size() - 1) en[ev[i].s] = i + 1;
      |         ~~~~~~~~~~~~~~~~~~~           
tra.cpp:123:5: note: in expansion of macro 'FOR'
  123 |     FOR(i, 0, ev.size() - 1) en[ev[i].s] = i + 1;
      |     ^~~
tra.cpp:6:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i, a, b) for(ll i = a; i <= b; i++)
......
  132 |     FOR(i, 1, ev.size()) pfx[i] = pfx[i - 1] + (rng[ev[i - 1].s].f != LONG_LONG_MAX);
      |         ~~~~~~~~~~~~~~~               
tra.cpp:132:5: note: in expansion of macro 'FOR'
  132 |     FOR(i, 1, ev.size()) pfx[i] = pfx[i - 1] + (rng[ev[i - 1].s].f != LONG_LONG_MAX);
      |     ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14680 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Correct 7 ms 14536 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14540 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 7 ms 14684 KB Output is correct
3 Correct 6 ms 14684 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14940 KB Output is correct
2 Correct 14 ms 15460 KB Output is correct
3 Correct 11 ms 15232 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 18480 KB Output is correct
2 Correct 95 ms 24208 KB Output is correct
3 Correct 42 ms 19060 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 22292 KB Output is correct
2 Correct 109 ms 26992 KB Output is correct
3 Correct 67 ms 22208 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 28112 KB Output is correct
2 Correct 168 ms 32848 KB Output is correct
3 Correct 225 ms 40352 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 35288 KB Output is correct
2 Correct 193 ms 35272 KB Output is correct
3 Correct 228 ms 42972 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 43208 KB Output is correct
2 Correct 327 ms 49564 KB Output is correct
3 Correct 487 ms 64068 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 57796 KB Output is correct
2 Correct 591 ms 68420 KB Output is correct
3 Correct 456 ms 61828 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 102388 KB Output is correct
2 Correct 668 ms 72784 KB Output is correct
3 Correct 955 ms 101036 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 48196 KB Output is correct
2 Correct 616 ms 79040 KB Output is correct
3 Correct 751 ms 86188 KB Output is correct
4 Correct 989 ms 111852 KB Output is correct