Submission #117645

#	Time	Username	Problem	Language	Result	Execution time	Memory
117645		JohnTitor	Traffic (CEOI11_tra)	C++11	100 / 100	720 ms	68576 KiB

tra

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
using ll=long long;
using ld=long double;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "Traffic"
int n, m, a, b;
class point{
public:
    int x, y;
    void input(){
        read(x);
        read(y);
    }
} p[300001];
bool good[300001];
vector <int> g[300001];
void pre_dfs(int u){
    good[u]=1;
    for(int v: g[u]) if(!good[v]) pre_dfs(v);
}
vector <int> rh;
vector <int> s;
int id[300001];
int done[300001];
int num[300001];
int low[300001];
int cnt;
int from[300001];
int first[300001];
int last[300001];
vector <int> h[300001];
int ccnt;
void dfs(int u){
    cnt++;
    num[u]=low[u]=cnt;
    done[u]=1;
    s.pb(u);
    for(int v: g[u]) if(!done[v]){
        dfs(v);
        low[u]=min(low[u], low[v]);
    }
    else if(done[v]!=2) low[u]=min(low[u], num[v]);
    if(low[u]==num[u]){
        int v;
        ccnt++;
        do{
            v=s.back();
            s.pop_back();
            done[v]=2;
            from[v]=ccnt;
        }
        while(v!=u);
    }
}
bool calculated[300001];
void dp(int u){
    if(calculated[u]) return;
    calculated[u]=1;
    for(int v: h[u]){
        dp(v);
        first[u]=min(first[u], first[v]);
        last[u]=max(last[u], last[v]);
    }
}
vector <pair <int, int>> ans;
int main(){
    #ifdef Uiharu
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Uiharu
    read(n);
    read(m);
    read(a);
    read(b);
    FOR(i, 1, n) p[i].input();
    {
        int u, v, t;
        FOR(i, 1, m){
            read(u);
            read(v);
            read(t);
            g[u].pb(v);
            if(t==2) g[v].pb(u);
        }
    }
    FOR(i, 1, n) if(!good[i]) if(p[i].x==0) pre_dfs(i);
    FOR(i, 1, n) if(good[i]) if(p[i].x==a) rh.pb(i);
    sort(rh.begin(), rh.end(), [](int a, int b){
        return p[a].y<p[b].y;
    });
    FOR(i, 1, n) if(!done[i]) dfs(i);
    FOR(u, 1, n) if(good[u]) for(int v: g[u]) if(good[v]) h[from[u]].pb(from[v]);
    FOR(u, 1, ccnt) first[u]=rh.size();
    FOR(u, 1, ccnt) last[u]=-1;
    FFOR(i, 0, rh.size()) first[from[rh[i]]]=min(first[from[rh[i]]], i);
    FFOR(i, 0, rh.size()) last[from[rh[i]]]=max(last[from[rh[i]]], i);
    FOR(i, 1, ccnt) dp(i);
    FOR(i, 1, n) if(p[i].x==0) ans.pb(mp(i, max(0, last[from[i]]-first[from[i]]+1)));
    sort(ans.begin(), ans.end(), [](pair <int, int> A, pair <int, int> B){
        return p[A.first].y>p[B.first].y;
    });
    for(auto x: ans) writeln(x.second);
}

Compilation message (stderr)

tra.cpp: In function 'int main()':
tra.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
tra.cpp:132:5: note: in expansion of macro 'FFOR'
     FFOR(i, 0, rh.size()) first[from[rh[i]]]=min(first[from[rh[i]]], i);
     ^~~~
tra.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
tra.cpp:133:5: note: in expansion of macro 'FFOR'
     FFOR(i, 0, rh.size()) last[from[rh[i]]]=max(last[from[rh[i]]], 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