oj.uz

Submission #117361

# Submission time Handle Problem Language Result Execution time Memory
117361 2019-06-15T16:21:55 Z imyujin Traffic (CEOI11_tra) C++14
100 / 100
 1317 ms 74524 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>

using namespace std;

#define MAXN 300005
#define MAXM 900005

int x[MAXN], y[MAXN];
int c[MAXM], d[MAXM], k[MAXM];
vector<int> e[MAXN], einv[MAXN];
int l[MAXN], r[MAXN], ln, rn;
bool ava[MAXN];
int mn[MAXN], mx[MAXN];
int chk[MAXN];

bool cmp(int a, int b){
	return y[a]<y[b];
}

void dfs(int p, int q){
	//printf("[%d %d]\n", p, q);
	chk[p]=q;
	for(auto a:e[p]) if(chk[a]==-1) dfs(a, q);
}

void dfsinv(int p){
	chk[p]=0;
	for(auto a:einv[p]) if(chk[a]==-1) dfsinv(a);
}

int main(){
	int n, m, A, B;

	scanf("%d%d%d%d", &n, &m, &A, &B);
	for(int i=1; i<=n; i++) scanf("%d%d", x+i, y+i);
	for(int i=0; i<m; i++) scanf("%d%d%d", c+i, d+i, k+i);

	for(int i=0; i<m; i++){
		e[c[i]].push_back(d[i]);
		einv[d[i]].push_back(c[i]);
		if(k[i]==2){
			e[d[i]].push_back(c[i]);
			einv[c[i]].push_back(d[i]);
		}
	}

	for(int i=1; i<=n; i++) if(x[i]==0) l[ln++]=i;
	sort(l, l+ln, cmp);
	for(int i=1; i<=n; i++) chk[i]=-1;
	for(int i=1; i<=n; i++) if(x[i]==A) dfsinv(i);
	for(int i=0; i<ln; i++) ava[i]=chk[l[i]]!=-1;
	for(int i=1; i<=n; i++) chk[i]=-1;
	for(int i=0; i<ln; i++) if(ava[i]&&chk[l[i]]==-1) dfs(l[i], i);
	for(int i=1; i<=n; i++) if(x[i]==A&&chk[i]!=-1) r[rn++]=i;
	sort(r, r+rn, cmp);

	for(int i=0; i<ln; i++){
		mn[i]=rn-1;
		mx[i]=0;
	}
	//for(int i=1; i<=n; i++) printf("%d*\n", chk[i]);
	//for(int i=0; i<rn; i++) printf("*%d", r[i]);
	for(int i=0; i<rn; i++) mx[chk[r[i]]]=i;
	//for(int i=0; i<ln; i++) printf("(%d)\n", mx[i]);
	for(int i=1; i<ln; i++) if(mx[i-1]>mx[i]) mx[i]=mx[i-1];
	for(int i=1; i<=n; i++) chk[i]=-1;
	for(int i=ln-1; i>=0; i--) dfs(l[i], i);
	for(int i=rn-1; i>=0; i--) mn[chk[r[i]]]=i;
	for(int i=ln-2; i>=0; i--) if(mn[i+1]<mn[i]) mn[i]=mn[i+1];

	//for(int i=0; i<ln; i++) printf("[%d %d]\n", mn[i], mx[i]);

	for(int i=ln-1; i>=0; i--) printf("%d\n", ava[i]?mx[i]-mn[i]+1:0);
	return 0;
}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:36:7: 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:37:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%d%d", x+i, y+i);
                          ~~~~~^~~~~~~~~~~~~~~~~~
tra.cpp:38:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<m; i++) scanf("%d%d%d", c+i, d+i, k+i);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14692 KB Output is correct
2 Correct 16 ms 15104 KB Output is correct
3 Correct 19 ms 14848 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 15608 KB Output is correct
2 Correct 70 ms 20268 KB Output is correct
3 Correct 43 ms 17628 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 17656 KB Output is correct
2 Correct 110 ms 22004 KB Output is correct
3 Correct 75 ms 20088 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 20580 KB Output is correct
2 Correct 158 ms 27540 KB Output is correct
3 Correct 249 ms 29384 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 22916 KB Output is correct
2 Correct 188 ms 27008 KB Output is correct
3 Correct 292 ms 30444 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 26744 KB Output is correct
2 Correct 330 ms 35704 KB Output is correct
3 Correct 606 ms 43640 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 33352 KB Output is correct
2 Correct 606 ms 50168 KB Output is correct
3 Correct 627 ms 44552 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1189 ms 48912 KB Output is correct
2 Correct 634 ms 52124 KB Output is correct
3 Correct 1216 ms 64568 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 25336 KB Output is correct
2 Correct 739 ms 55612 KB Output is correct
3 Correct 960 ms 57752 KB Output is correct
4 Correct 1317 ms 74524 KB Output is correct