oj.uz

Submission #173695

# Submission time Handle Problem Language Result Execution time Memory
173695 2020-01-05T06:03:49 Z jhnah917 Traffic (CEOI11_tra) C++14
100 / 100
 1235 ms 70564 KB 
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n, m;
ll a, b;

int arr[303030]; //1 : left, 2 : right
p v[303030];
vector<int> le, ri;
int rid[303030];
vector<int> g[303030], rev[303030];

int chk[303030];
int del[303030];
int up[303030], down[303030];

bool ycmp(int a, int b){ return v[a].y < v[b].y; }

void removeLeft(){
    memset(chk, 0, sizeof chk);
    queue<int> q;
    for(auto i : le) q.push(i), chk[i] = 1;
    while(q.size()){
        int now = q.front(); q.pop();
        for(auto nxt : g[now]){
            if(chk[nxt]) continue;
            q.push(nxt); chk[nxt] = 1;
        }
    }
    for(auto i : ri) if(!chk[i]) del[i] = 1;
}

void removeRight(){
    memset(chk, 0, sizeof chk);
    queue<int> q;
    for(auto i : ri) q.push(i), chk[i] = 1;
    while(q.size()){
        int now = q.front(); q.pop();
        for(auto nxt : rev[now]){
            if(chk[nxt]) continue;
            q.push(nxt); chk[nxt] = 1;
        }
    }
    for(auto i : le) if(!chk[i]) del[i] = 1;
}

int dfs_up(int v){
    chk[v] = 1;
    int ret = -1;
    if(arr[v] == 2) ret = v;
    for(auto i : g[v]){
        if(chk[i]) continue;
        int t = dfs_up(i);
        if(t == -1) continue;
        if(ret == -1 || ::v[ret].y < ::v[t].y) ret = t;
    }
    return ret;
}

int dfs_down(int v){
    chk[v] = 1;
    int ret= -1;
    if(arr[v] == 2) ret = v;
    for(auto i : g[v]){
        if(chk[i]) continue;
        int t = dfs_down(i);
        if(t == -1) continue;
        if(ret == -1 || ::v[ret].y > ::v[t].y) ret = t;
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> a >> b;
    for(int i=1; i<=n; i++){
        ll x, y; cin >> x >> y;
        v[i] = {x, y};
        if(x == 0) le.push_back(i), arr[i] = 1;
        else if(x == a) ri.push_back(i), arr[i] = 2;
    }
    for(int i=1; i<=m; i++){
        int s, e, x ;cin >> s >> e >> x;
        g[s].push_back(e); rev[e].push_back(s);
        if(x == 2) g[e].push_back(s), rev[s].push_back(e);
    }
    removeLeft(); removeRight();
    le.clear(); ri.clear();
    for(int i=1; i<=n; i++){
        if(del[i]) continue;
        if(v[i].x == 0) le.push_back(i);
        if(v[i].x == a) ri.push_back(i);
    }
    sort(le.begin(), le.end(), ycmp);
    sort(ri.begin(), ri.end(), ycmp);
    for(int i=0; i<ri.size(); i++){
        rid[ri[i]] = i+1;
    }

    memset(chk, 0, sizeof chk);
    for(int i=0; i<le.size(); i++){
        int t = dfs_up(le[i]);
        if(t == -1) up[le[i]] = up[le[i-1]];
        else up[le[i]] = rid[t];
        
    }
    memset(chk, 0, sizeof chk);
    for(int i=le.size()-1; i>=0; i--){
        int t = dfs_down(le[i]);
        if(t == -1) down[le[i]] = down[le[i+1]];
        else down[le[i]] = rid[t];
    }
    
    for(int i=1; i<=n; i++) if(v[i].x == 0 && del[i]) le.push_back(i);
    sort(le.rbegin(), le.rend(), ycmp);
    for(auto i : le){
        if(del[i]) cout << 0 << "\n";
        else cout << up[i] - down[i] + 1 << "\n";
    }
}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:101:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<ri.size(); i++){
                  ~^~~~~~~~~~
tra.cpp:106:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<le.size(); i++){
                  ~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15864 KB Output is correct
2 Correct 16 ms 15864 KB Output is correct
3 Correct 17 ms 15736 KB Output is correct
4 Correct 17 ms 15864 KB Output is correct
5 Correct 16 ms 15864 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15736 KB Output is correct
2 Correct 17 ms 15868 KB Output is correct
3 Correct 16 ms 15736 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15736 KB Output is correct
2 Correct 18 ms 15900 KB Output is correct
3 Correct 17 ms 15864 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15996 KB Output is correct
2 Correct 23 ms 16504 KB Output is correct
3 Correct 21 ms 16200 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 18032 KB Output is correct
2 Correct 92 ms 22120 KB Output is correct
3 Correct 52 ms 18912 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 20828 KB Output is correct
2 Correct 118 ms 23956 KB Output is correct
3 Correct 83 ms 21752 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 25652 KB Output is correct
2 Correct 195 ms 29756 KB Output is correct
3 Correct 324 ms 30076 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 28388 KB Output is correct
2 Correct 212 ms 29376 KB Output is correct
3 Correct 318 ms 30840 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 35836 KB Output is correct
2 Correct 348 ms 39856 KB Output is correct
3 Correct 623 ms 42932 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 47608 KB Output is correct
2 Correct 627 ms 54248 KB Output is correct
3 Correct 706 ms 45432 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1211 ms 64948 KB Output is correct
2 Correct 661 ms 55848 KB Output is correct
3 Correct 1132 ms 61324 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 39676 KB Output is correct
2 Correct 753 ms 59592 KB Output is correct
3 Correct 949 ms 56184 KB Output is correct
4 Correct 1235 ms 70564 KB Output is correct