oj.uz

Submission #237403

# Submission time Handle Problem Language Result Execution time Memory
237403 2020-06-06T13:34:52 Z keta_tsimakuridze One-Way Streets (CEOI17_oneway) C++14
100 / 100
 401 ms 36856 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m,k,u,v,mn[100005],ind[100005],fix[100005],bridge[100005],F[100005],sum[100005],timer,tmin[100005],q;
char ans[100005];
vector<pair<int,pair<int,int> > >V[100005],B[100005];
map<int,int>FX[100005];
void dfs(int u,int p) {
	fix[u]=1;
	timer++;
	tmin[u]=mn[u]=timer;
	for(int i=0; i<V[u].size(); i++) {
		int v=V[u][i].first;
		if(v==p) continue;
		if(fix[v]==0) {
			dfs(v,u);
			mn[u]=min(mn[u],mn[v]);
			if(mn[v]>tmin[u] && FX[v][u]==1) {
				bridge[V[u][i].second.first]=1;
				F[v]=1;
				F[u]=1;

			}
		} else mn[u]=min(mn[u],tmin[v]);

	}
//	cout<<u<<"++"<<mn[u]<<endl;

}
void dfs1(int u,int p,int nm) {
	if(nm==1)fix[u]=2;
	else fix[u]=4;
	if(nm==1)ind[u]=p;
	for(int i=0; i<V[u].size(); i++) {
		int c=0;
		if(nm==2) c=4;
		else c=2;
		if(nm==2)if(bridge[V[u][i].second.first]!=0 &&fix[V[u][i].first]!=c ) {
				int v=V[u][i].first;
				B[ind[v]].push_back({p,{V[u][i].second.first,V[u][i].second.second}});
				B[p].push_back({ind[v],{V[u][i].second.first,1-V[u][i].second.second}});
			}
		if(fix[V[u][i].first]!=c && bridge[V[u][i].second.first]==0) {
			dfs1(V[u][i].first,p,nm);
		}

	}
}
void dfs2(int u,int p) {
	fix[u]=3;
	for(int i=0; i<B[u].size(); i++) {

		int v=B[u][i].first;
		if(v!=p ) {
			dfs2(v,u);
			sum[u]+=sum[v];

			if(sum[v]>0) {
				if(B[u][i].second.second==1) {
					ans[B[u][i].second.first]='R';
				} else ans[B[u][i].second.first]='L';
			}
			if(sum[v]<0) {
				if(B[u][i].second.second==1) {
					ans[B[u][i].second.first]='L';
				} else ans[B[u][i].second.first]='R';

			}
		}
	}
}
int main() {
	cin>>n>>m;
	
	for(k=1; k<=m; k++) {
		cin>>u>>v; FX[u][v]++;
		FX[v][u]++;
		V[u].push_back({v,{k,1}});
		V[v].push_back({u,{k,0}});
		ans[k]='B';
	}

	for(k=1; k<=n; k++)
		if(!fix[k])
			dfs(k,0);


	for(k=1; k<=n; k++) {
		if(F[k] && fix[k]!=2)dfs1(k,k,1);
	}
	for(k=1; k<=n; k++) {
		if(F[k] && fix[k]!=4)dfs1(k,k,2);
	}
	cin>>q;
	while(q--) {
		cin>>u>>v;
		sum[ind[u]]++;
		sum[ind[v]]--;
	}

	for(k=1; k<=n; k++) {
		if(fix[ind[k]]!=3 ) {
			dfs2(ind[k],0);
		}
	}
	for(k=1; k<=m; k++) {
		cout<<ans[k];
	}
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:11:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<V[u].size(); i++) {
               ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs1(int, int, int)':
oneway.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<V[u].size(); i++) {
               ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<B[u].size(); i++) {
               ~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 11 ms 9984 KB Output is correct
4 Correct 12 ms 9984 KB Output is correct
5 Correct 12 ms 9984 KB Output is correct
6 Correct 11 ms 9856 KB Output is correct
7 Correct 11 ms 9984 KB Output is correct
8 Correct 12 ms 9984 KB Output is correct
9 Correct 11 ms 9984 KB Output is correct
10 Correct 11 ms 9856 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 11 ms 9984 KB Output is correct
4 Correct 12 ms 9984 KB Output is correct
5 Correct 12 ms 9984 KB Output is correct
6 Correct 11 ms 9856 KB Output is correct
7 Correct 11 ms 9984 KB Output is correct
8 Correct 12 ms 9984 KB Output is correct
9 Correct 11 ms 9984 KB Output is correct
10 Correct 11 ms 9856 KB Output is correct
11 Correct 206 ms 26488 KB Output is correct
12 Correct 230 ms 28408 KB Output is correct
13 Correct 286 ms 29944 KB Output is correct
14 Correct 290 ms 31288 KB Output is correct
15 Correct 292 ms 31660 KB Output is correct
16 Correct 275 ms 31736 KB Output is correct
17 Correct 268 ms 32888 KB Output is correct
18 Correct 294 ms 31736 KB Output is correct
19 Correct 241 ms 33912 KB Output is correct
20 Correct 210 ms 26548 KB Output is correct
21 Correct 172 ms 26232 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 11 ms 9984 KB Output is correct
4 Correct 12 ms 9984 KB Output is correct
5 Correct 12 ms 9984 KB Output is correct
6 Correct 11 ms 9856 KB Output is correct
7 Correct 11 ms 9984 KB Output is correct
8 Correct 12 ms 9984 KB Output is correct
9 Correct 11 ms 9984 KB Output is correct
10 Correct 11 ms 9856 KB Output is correct
11 Correct 206 ms 26488 KB Output is correct
12 Correct 230 ms 28408 KB Output is correct
13 Correct 286 ms 29944 KB Output is correct
14 Correct 290 ms 31288 KB Output is correct
15 Correct 292 ms 31660 KB Output is correct
16 Correct 275 ms 31736 KB Output is correct
17 Correct 268 ms 32888 KB Output is correct
18 Correct 294 ms 31736 KB Output is correct
19 Correct 241 ms 33912 KB Output is correct
20 Correct 210 ms 26548 KB Output is correct
21 Correct 172 ms 26232 KB Output is correct
22 Correct 340 ms 34016 KB Output is correct
23 Correct 335 ms 32504 KB Output is correct
24 Correct 401 ms 32888 KB Output is correct
25 Correct 329 ms 36856 KB Output is correct
26 Correct 335 ms 33656 KB Output is correct
27 Correct 332 ms 32760 KB Output is correct
28 Correct 145 ms 14712 KB Output is correct
29 Correct 278 ms 27000 KB Output is correct
30 Correct 266 ms 27512 KB Output is correct
31 Correct 297 ms 28244 KB Output is correct
32 Correct 268 ms 28536 KB Output is correct