oj.uz

Submission #244599

# Submission time Handle Problem Language Result Execution time Memory
244599 2020-07-04T10:52:37 Z TadijaSebez Traffic (CEOI11_tra) C++11
100 / 100
 1274 ms 74616 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 21504 KB Output is correct
2 Correct 17 ms 21504 KB Output is correct
3 Correct 19 ms 21504 KB Output is correct
4 Correct 17 ms 21504 KB Output is correct
5 Correct 17 ms 21504 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 21376 KB Output is correct
2 Correct 18 ms 21504 KB Output is correct
3 Correct 17 ms 21504 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21504 KB Output is correct
2 Correct 18 ms 21504 KB Output is correct
3 Correct 20 ms 21504 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21632 KB Output is correct
2 Correct 22 ms 22144 KB Output is correct
3 Correct 24 ms 21888 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 23160 KB Output is correct
2 Correct 80 ms 27544 KB Output is correct
3 Correct 49 ms 24184 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 25592 KB Output is correct
2 Correct 121 ms 29176 KB Output is correct
3 Correct 73 ms 26620 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 29328 KB Output is correct
2 Correct 182 ms 34740 KB Output is correct
3 Correct 306 ms 34040 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 32120 KB Output is correct
2 Correct 181 ms 34168 KB Output is correct
3 Correct 285 ms 34768 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 38128 KB Output is correct
2 Correct 333 ms 43380 KB Output is correct
3 Correct 664 ms 45944 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 47608 KB Output is correct
2 Correct 603 ms 57196 KB Output is correct
3 Correct 640 ms 47864 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1149 ms 64888 KB Output is correct
2 Correct 637 ms 59628 KB Output is correct
3 Correct 1125 ms 63224 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 39832 KB Output is correct
2 Correct 692 ms 62724 KB Output is correct
3 Correct 930 ms 57980 KB Output is correct
4 Correct 1274 ms 74616 KB Output is correct