Submission #197483

# Submission time Handle Problem Language Result Execution time Memory
197483 2020-01-21T12:48:19 Z mhy908 Traffic (CEOI11_tra) C++14
0 / 100
1111 ms 59216 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));
    }
    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:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<westcoast.size(); i++){
                  ~^~~~~~~~~~~~~~~~~
tra.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<eastcoast.size(); i++){
                  ~^~~~~~~~~~~~~~~~~
tra.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<wc.size(); i++){
                  ~^~~~~~~~~~
tra.cpp:94: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:33: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);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 16 ms 14840 KB Output is correct
2 Incorrect 16 ms 14712 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 14712 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 14712 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 14840 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 16248 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 19036 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 239 ms 22820 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 259 ms 25756 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 334 ms 31896 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 519 ms 41724 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1111 ms 59216 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 291 ms 33328 KB Output isn't correct
2 Halted 0 ms 0 KB -