oj.uz

Submission #117645

# Submission time Handle Problem Language Result Execution time Memory
117645 2019-06-17T03:46:53 Z JohnTitor Traffic (CEOI11_tra) C++11
100 / 100
 720 ms 68576 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14464 KB Output is correct
2 Correct 13 ms 14464 KB Output is correct
3 Correct 14 ms 14464 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 13 ms 14464 KB Output is correct
3 Correct 14 ms 14416 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 14 ms 14592 KB Output is correct
3 Correct 14 ms 14592 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14720 KB Output is correct
2 Correct 18 ms 15036 KB Output is correct
3 Correct 17 ms 14848 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16888 KB Output is correct
2 Correct 51 ms 20276 KB Output is correct
3 Correct 37 ms 17540 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 18808 KB Output is correct
2 Correct 67 ms 21756 KB Output is correct
3 Correct 55 ms 20484 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 23416 KB Output is correct
2 Correct 125 ms 27512 KB Output is correct
3 Correct 150 ms 27180 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 25196 KB Output is correct
2 Correct 133 ms 26644 KB Output is correct
3 Correct 171 ms 27784 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 32328 KB Output is correct
2 Correct 265 ms 37484 KB Output is correct
3 Correct 392 ms 39476 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 43268 KB Output is correct
2 Correct 440 ms 49520 KB Output is correct
3 Correct 398 ms 41848 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 49248 KB Output is correct
2 Correct 509 ms 50652 KB Output is correct
3 Correct 720 ms 55792 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 37484 KB Output is correct
2 Correct 466 ms 56400 KB Output is correct
3 Correct 646 ms 52984 KB Output is correct
4 Correct 712 ms 68576 KB Output is correct