Submission #197506

#	Time	Username	Problem	Language	Result	Execution time	Memory
197506		mhy908	Traffic (CEOI11_tra)	C++14	100 / 100	1263 ms	60820 KiB

tra

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

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 / 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