oj.uz

Submission #117359

# Submission time Handle Problem Language Result Execution time Memory
117359 2019-06-15T16:12:24 Z imyujin Traffic (CEOI11_tra) C++14
0 / 100
 1200 ms 63760 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<rn; 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=rn-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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 14592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 16092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 18936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 22880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 26600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 336 ms 32576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 486 ms 42368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1200 ms 63760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 269 ms 32460 KB Output isn't correct
2 Halted 0 ms 0 KB -