oj.uz

Submission #197506

# Submission time Handle Problem Language Result Execution time Memory
197506 2020-01-21T13:19:10 Z mhy908 Traffic (CEOI11_tra) C++14
100 / 100
 1263 ms 60820 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=9000000000000000000;
const int inf=2000000000;
vector<int> link[300010], rlink[300010];
vector<pii> westcoast, eastcoast, wc, ec;
pii point[300010];
int n, m, a, b;
int sou[300010], nor[300010];
bool ch[300010];
int que[300010], re, fr;
int main(){
    scanf("%d %d %d %d", &n, &m, &a, &b);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &point[i].F, &point[i].S);
        if(point[i].F==0)westcoast.pb(mp(point[i].S, i));
        if(point[i].F==a)eastcoast.pb(mp(point[i].S, i));
    }
    sortvec(westcoast);
    sortvec(eastcoast);
    for(int i=1; i<=m; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if(c==1){
            link[a].pb(b);
            rlink[b].pb(a);
        }
        else{
            link[a].pb(b);
            link[b].pb(a);
            rlink[a].pb(b);
            rlink[b].pb(a);
        }
    }
    for(int i=0; i<westcoast.size(); i++){
        que[++re]=westcoast[i].S;
        ch[que[re]]=true;
    }
    for(fr=1; fr<=re; fr++){
        if(point[que[fr]].F==a)ec.pb(mp(point[que[fr]].S, que[fr]));
        for(auto i:link[que[fr]]){
            if(ch[i])continue;
            ch[i]=true;
            que[++re]=i;
        }
    }
    memset(ch, 0, sizeof ch);
    re=fr=0;
    for(int i=0; i<eastcoast.size(); i++){
        que[++re]=eastcoast[i].S;
        ch[que[re]]=true;
    }
    for(fr=1; fr<=re; fr++){
        if(point[que[fr]].F==0)wc.pb(mp(point[que[fr]].S, que[fr]));
        for(auto i:rlink[que[fr]]){
            if(ch[i])continue;
            ch[i]=true;
            que[++re]=i;
        }
    }
    sortvec(ec);
    sortvec(wc);
    memset(ch, 0, sizeof ch);
    re=0;
    fr=1;
    for(int i=0; i<wc.size(); i++){
        if(i)nor[wc[i].S]=nor[wc[i-1].S];
        if(ch[wc[i].S])continue;
        que[++re]=wc[i].S;
        ch[wc[i].S]=true;
        for(; fr<=re; fr++){
            if(point[que[fr]].F==a)nor[wc[i].S]=max(nor[wc[i].S], (int)(upper_bound(all(ec), mp(point[que[fr]].S, -inf))-ec.begin()));
            for(auto j:link[que[fr]]){
                if(ch[j])continue;
                ch[j]=true;
                que[++re]=j;
            }
        }
    }
    reverse(all(wc));
    memset(ch, 0, sizeof ch);
    re=0;
    fr=1;
    for(int i=0; i<wc.size(); i++){
        if(i)sou[wc[i].S]=sou[wc[i-1].S];
        else sou[wc[i].S]=ec.size()-1;
        if(ch[wc[i].S])continue;
        que[++re]=wc[i].S;
        ch[wc[i].S]=true;
        for(; fr<=re; fr++){
            if(point[que[fr]].F==a)sou[wc[i].S]=min(sou[wc[i].S], (int)(upper_bound(all(ec), mp(point[que[fr]].S, -inf))-ec.begin()));
            for(auto j:link[que[fr]]){
                if(ch[j])continue;
                ch[j]=true;
                que[++re]=j;
            }
        }
    }
    reverse(all(wc));
    for(int i=westcoast.size()-1; i>=0; i--){
        if(binary_search(all(wc), westcoast[i]))printf("%d\n", nor[westcoast[i].S]-sou[westcoast[i].S]+1);
        else puts("0");
    }
}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<westcoast.size(); i++){
                  ~^~~~~~~~~~~~~~~~~
tra.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<eastcoast.size(); i++){
                  ~^~~~~~~~~~~~~~~~~
tra.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<wc.size(); i++){
                  ~^~~~~~~~~~
tra.cpp:96:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<wc.size(); i++){
                  ~^~~~~~~~~~
tra.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &n, &m, &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tra.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &point[i].F, &point[i].S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tra.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14716 KB Output is correct
2 Correct 16 ms 14840 KB Output is correct
3 Correct 15 ms 14840 KB Output is correct
4 Correct 15 ms 14712 KB Output is correct
5 Correct 15 ms 14712 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14712 KB Output is correct
2 Correct 15 ms 14712 KB Output is correct
3 Correct 16 ms 14712 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14712 KB Output is correct
2 Correct 16 ms 14840 KB Output is correct
3 Correct 17 ms 14712 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14840 KB Output is correct
2 Correct 22 ms 15400 KB Output is correct
3 Correct 20 ms 15096 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16128 KB Output is correct
2 Correct 90 ms 20444 KB Output is correct
3 Correct 52 ms 17660 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 18904 KB Output is correct
2 Correct 119 ms 21836 KB Output is correct
3 Correct 81 ms 20004 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 22768 KB Output is correct
2 Correct 216 ms 25964 KB Output is correct
3 Correct 287 ms 27756 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 25600 KB Output is correct
2 Correct 206 ms 26352 KB Output is correct
3 Correct 307 ms 28460 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 32092 KB Output is correct
2 Correct 360 ms 35000 KB Output is correct
3 Correct 606 ms 39800 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 41512 KB Output is correct
2 Correct 633 ms 48432 KB Output is correct
3 Correct 669 ms 41516 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1145 ms 59128 KB Output is correct
2 Correct 684 ms 49816 KB Output is correct
3 Correct 1089 ms 57520 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 33340 KB Output is correct
2 Correct 739 ms 50476 KB Output is correct
3 Correct 921 ms 51800 KB Output is correct
4 Correct 1263 ms 60820 KB Output is correct