Submission #117361

#	Time	Username	Problem	Language	Result	Execution time	Memory
117361		imyujin	Traffic (CEOI11_tra)	C++14	100 / 100	1317 ms	74524 KiB

tra

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

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