Submission #173695

#	Time	Username	Problem	Language	Result	Execution time	Memory
173695		jhnah917	Traffic (CEOI11_tra)	C++14	100 / 100	1235 ms	70564 KiB

tra

#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 (stderr)

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 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9