oj.uz

Submission #1066130

# Submission time Handle Problem Language Result Execution time Memory
1066130 2024-08-19T15:16:18 Z codexistent Traffic (CEOI11_tra) C++14
100 / 100
 1004 ms 107828 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]);
        for(ll i2 : radj[ts[i]]) {
            rw[ts[i]] |= rw[find(i2)];
        }
    }
 
    // 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);
            }
        }
    }
 
    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++)
......
  117 |     FOR(i, 0, ev.size() - 1) en[ev[i].s] = i + 1;
      |         ~~~~~~~~~~~~~~~~~~~           
tra.cpp:117:5: note: in expansion of macro 'FOR'
  117 |     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++)
......
  126 |     FOR(i, 1, ev.size()) pfx[i] = pfx[i - 1] + (rng[ev[i - 1].s].f != LONG_LONG_MAX);
      |         ~~~~~~~~~~~~~~~               
tra.cpp:126:5: note: in expansion of macro 'FOR'
  126 |     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 7 ms 14428 KB Output is correct
2 Correct 6 ms 14540 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Correct 7 ms 14424 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 7 ms 14428 KB Output is correct
2 Correct 6 ms 14540 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 7 ms 14428 KB Output is correct
2 Correct 7 ms 14680 KB Output is correct
3 Correct 6 ms 14560 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14940 KB Output is correct
2 Correct 13 ms 15444 KB Output is correct
3 Correct 10 ms 15180 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 18516 KB Output is correct
2 Correct 91 ms 24220 KB Output is correct
3 Correct 43 ms 18904 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 22100 KB Output is correct
2 Correct 112 ms 26960 KB Output is correct
3 Correct 62 ms 22312 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 27856 KB Output is correct
2 Correct 168 ms 32592 KB Output is correct
3 Correct 220 ms 39628 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 35288 KB Output is correct
2 Correct 185 ms 35032 KB Output is correct
3 Correct 234 ms 41944 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 43460 KB Output is correct
2 Correct 336 ms 47948 KB Output is correct
3 Correct 490 ms 62344 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 58028 KB Output is correct
2 Correct 571 ms 65944 KB Output is correct
3 Correct 469 ms 59780 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 943 ms 102640 KB Output is correct
2 Correct 685 ms 70468 KB Output is correct
3 Correct 928 ms 97220 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 48204 KB Output is correct
2 Correct 615 ms 76476 KB Output is correct
3 Correct 765 ms 83296 KB Output is correct
4 Correct 1004 ms 107828 KB Output is correct