Submission #244599

#	Time	Username	Problem	Language	Result	Execution time	Memory
244599		TadijaSebez	Traffic (CEOI11_tra)	C++11	100 / 100	1274 ms	74616 KiB

tra

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=300050;
vector<int> E[N],R[N];
void AddEdge(int u,int v){E[u].pb(v);R[v].pb(u);}
bool is_east[N],is_west[N];
void RDFS(int u,bool was[]){
	was[u]=1;
	for(int v:R[u])if(!was[v])RDFS(v,was);
}
vector<int> ids[N];
void DFS(int u,bool was[],int src){
	was[u]=1;
	if(is_east[u])ids[u].pb(src);
	for(int v:E[u])if(!was[v])DFS(v,was,src);
}
int x[N],y[N],ord[N],ans[N];
void Add(int l,int r){ans[l]++;ans[r+1]--;}
bool rch[N],was[N];
int main(){
	int n,m,A,B;scanf("%i %i %i %i",&n,&m,&A,&B);
	vector<int> east,west;
	for(int i=1;i<=n;i++){
		scanf("%i %i",&x[i],&y[i]);
		if(x[i]==0)west.pb(i),is_west[i]=1;
		if(x[i]==A)east.pb(i),is_east[i]=1;
	}
	sort(west.begin(),west.end(),[&](int i,int j){return y[i]>y[j];});
	for(int i=0;i<west.size();i++)ord[west[i]]=i+1;
	for(int i=1;i<=m;i++){
		int u,v,k;scanf("%i %i %i",&u,&v,&k);
		AddEdge(u,v);
		if(k==2)AddEdge(v,u);
	}
	for(int i:east)RDFS(i,rch);
	for(int i=0;i<west.size();i++)DFS(west[i],was,i+1);
	for(int i=1;i<=n;i++)was[i]=0;
	for(int i=(int)west.size()-1;i>=0;i--)DFS(west[i],was,i+1);
	for(int i:east){
		if(was[i]){
			assert(ids[i].size()==2);
			Add(ids[i][0],ids[i][1]);
		}
	}
	for(int i=1;i<=west.size();i++){
		ans[i]+=ans[i-1];
		printf("%i\n",rch[west[i-1]]?ans[i]:0);
	}
	return 0;
}

Compilation message (stderr)

tra.cpp: In function 'int main()':
tra.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<west.size();i++)ord[west[i]]=i+1;
              ~^~~~~~~~~~~~
tra.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<west.size();i++)DFS(west[i],was,i+1);
              ~^~~~~~~~~~~~
tra.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<=west.size();i++){
              ~^~~~~~~~~~~~~
tra.cpp:22:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n,m,A,B;scanf("%i %i %i %i",&n,&m,&A,&B);
              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
tra.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&x[i],&y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
tra.cpp:32:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u,v,k;scanf("%i %i %i",&u,&v,&k);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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