oj.uz

Submission #236641

# Submission time Handle Problem Language Result Execution time Memory
236641 2020-06-02T16:59:27 Z bharat2002 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 212 ms 33000 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5 + 2;
const int N2=19;
const int mod=1e9 + 7;
const int inf=INT_MAX;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl 
int n, m, P;vector< pii > adj[N], adjlist[N];
pii arr[N];int disc[N], low[N], cur, cno[N], p[N][N2], addu[N], addv[N], sub[N],ent[N], ex[N], depth[N];
bool art[N];bool dup[N];string ans;
vector< pii > edges;
void dfs(int i, int p)
{
	disc[i]=cur++;low[i]=disc[i];
	int ct=0;
	for(auto j:adj[i])
	{
		if(j.f==p) ct++;
		if(j.f==p) continue;
		if(disc[j.f]==inf)
		{
			dfs(j.f, i);
			if(low[j.f]>disc[i]) art[j.s]=1;
			low[i]=min(low[i], low[j.f]);
		}
		else
		{
			low[i]=min(disc[j.f], low[i]);
		}
	}
	if(ct>1)
		for(auto j:adj[i]) 
			if(j.f==p) dup[j.s]=1;
}
void dfs2(int i)
{
	cno[i]=cur;
	for(auto j:adj[i])
	{
		if(art[j.s]) adjlist[cur].push_back(j);
		if(cno[j.f]!=-1||art[j.s]) continue;
		dfs2(j.f);
	}
}
void dfs3(int i)
{
	for(auto j:adjlist[i])
	{
		if(j.f==p[i][0]) continue;
		depth[j.f]=depth[i]+1;
		p[j.f][0]=i;dfs3(j.f);
	}
}
int LCA(int u, int v)
{
	if(depth[u]>depth[v]) swap(u, v);
	int diff=depth[v]-depth[u];
	for(int i=N2-1;i>=0;i--)
	{
		if((1<<i)<=diff)
		{
			diff-=(1<<i);v=p[v][i];
		}
	}
	if(u==v) return u;
	for(int i=N2-1;i>=0;i--)
	{
		if(p[u][i]!=p[v][i]) {u=p[u][i];v=p[v][i];}
	}
	return p[u][0];
}
int curr;
void dfsf(int i)
{
	int pind;
	for(auto j:adjlist[i])
	{
		if(j.f==p[i][0]) {
			pind=j.s;
			continue;}
		dfsf(j.f);ex[i]+=ex[j.f];ent[i]+=ent[j.f];
	}
	ent[i]-=sub[i];ex[i]-=sub[i];ent[i]+=addv[i];ex[i]+=addu[i];
	if(i==1) return;
	if(ent[i]>0)
	{
		int u=edges[pind].f, v=edges[pind].s;
		u=cno[u];v=cno[v];
		if(v==i) ans[pind]='R';
		else ans[pind]='L';
	}
	else if(ex[i]>0)
	{
		int u=edges[pind].f, v=edges[pind].s;
		u=cno[u];v=cno[v];
		if(v==i) ans[pind]='L';
		else ans[pind]='R';	
	}
}
void solve()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		art[i]=0;dup[i]=0;
		int u, v;cin>>u>>v;adj[u].push_back(mp(v, i));adj[v].push_back(mp(u, i));edges.push_back(mp(u, v));
	}
	cin>>P;
	for(int i=0;i<m;i++) ans.push_back('B');
	for(int i=1;i<=P;i++) cin>>arr[i].f>>arr[i].s;cur=1;
	for(int i=1;i<=n;i++) {disc[i]=inf;cno[i]=p[i][0]=-1;addu[i]=addv[i]=ent[i]=ex[i]=0;}
	for(int i=1;i<=n;i++)
	{
		if(disc[i]!=inf) continue;
		cur=1;
		dfs(i, 1);
	}
	for(int i=0;i<m;i++) 
	if(dup[i]) art[i]=0;cur=1;
	for(int i=1;i<=n;i++)
	{
		if(cno[i]==-1) {dfs2(i);cur++;}
	}
	for(int i=1;i<cur;i++)
		for(auto &j:adjlist[i]) j.f=cno[j.f];
	cur--;
	for(int i=1;i<cur;i++)
	{	
		if(p[i][0]!=-1) continue;
		p[i][0]=i;depth[i]=0;
		dfs3(i);
	}
	for(int j=1;j<N2;j++)
		for(int i=1;i<=n;i++) p[i][j]=p[p[i][j-1]][j-1];
	for(int j=1;j<=P;j++)
	{
		pii i=arr[j];
		i.f=cno[i.f], i.s=cno[i.s];
		addu[i.f]++;addv[i.s]++;
		int u=LCA(i.f, i.s);
		sub[u]++;
	}
	for(int i=1;i<cur;i++)
	{
		if(p[i][0]!=i) continue;
		curr=i;
		dfsf(i);
	}
	cout<<ans<<endl;
}
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	solve();
}

Compilation message

oneway.cpp: In function 'void solve()':
oneway.cpp:115:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int i=1;i<=P;i++) cin>>arr[i].f>>arr[i].s;cur=1;
  ^~~
oneway.cpp:115:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int i=1;i<=P;i++) cin>>arr[i].f>>arr[i].s;cur=1;
                                                ^~~
oneway.cpp:124:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(dup[i]) art[i]=0;cur=1;
  ^~
oneway.cpp:124:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(dup[i]) art[i]=0;cur=1;
                      ^~~
oneway.cpp:123:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int i=0;i<m;i++) 
  ^~~
oneway.cpp:124:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  if(dup[i]) art[i]=0;cur=1;
                      ^~~
oneway.cpp: In function 'void dfsf(int)':
oneway.cpp:92:19: warning: 'pind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int u=edges[pind].f, v=edges[pind].s;
                   ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5248 KB Output is correct
7 Correct 8 ms 5376 KB Output is correct
8 Correct 8 ms 5376 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 8 ms 5248 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5248 KB Output is correct
7 Correct 8 ms 5376 KB Output is correct
8 Correct 8 ms 5376 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 8 ms 5248 KB Output is correct
11 Correct 54 ms 13548 KB Output is correct
12 Correct 54 ms 15592 KB Output is correct
13 Correct 65 ms 18668 KB Output is correct
14 Correct 81 ms 22508 KB Output is correct
15 Correct 101 ms 23792 KB Output is correct
16 Correct 128 ms 25452 KB Output is correct
17 Correct 122 ms 27096 KB Output is correct
18 Correct 126 ms 25452 KB Output is correct
19 Correct 118 ms 28652 KB Output is correct
20 Correct 58 ms 17004 KB Output is correct
21 Correct 56 ms 16620 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5248 KB Output is correct
7 Correct 8 ms 5376 KB Output is correct
8 Correct 8 ms 5376 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 8 ms 5248 KB Output is correct
11 Correct 54 ms 13548 KB Output is correct
12 Correct 54 ms 15592 KB Output is correct
13 Correct 65 ms 18668 KB Output is correct
14 Correct 81 ms 22508 KB Output is correct
15 Correct 101 ms 23792 KB Output is correct
16 Correct 128 ms 25452 KB Output is correct
17 Correct 122 ms 27096 KB Output is correct
18 Correct 126 ms 25452 KB Output is correct
19 Correct 118 ms 28652 KB Output is correct
20 Correct 58 ms 17004 KB Output is correct
21 Correct 56 ms 16620 KB Output is correct
22 Correct 212 ms 29420 KB Output is correct
23 Correct 186 ms 27376 KB Output is correct
24 Correct 189 ms 27368 KB Output is correct
25 Correct 182 ms 33000 KB Output is correct
26 Correct 193 ms 29036 KB Output is correct
27 Correct 172 ms 27624 KB Output is correct
28 Correct 43 ms 10348 KB Output is correct
29 Correct 84 ms 18408 KB Output is correct
30 Correct 82 ms 18540 KB Output is correct
31 Correct 82 ms 18920 KB Output is correct
32 Correct 105 ms 23404 KB Output is correct