| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 197483 |
2020-01-21T12:48:19 Z |
mhy908 |
Traffic (CEOI11_tra) |
C++14 |
|
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 |
- |
