oj.uz

Submission #147291

# Submission time Handle Problem Language Result Execution time Memory
147291 2019-08-28T18:29:31 Z MvC One-Way Streets (CEOI17_oneway) C++11
100 / 100
 234 ms 30712 KB 
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "boxes.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<61);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int n,m,i,fin[nmax],fup[nmax],br[nmax],x,y,l,tin,ex[nmax],ey[nmax],par[nmax][20],c[nmax],k,in[nmax],out[nmax],z,up[nmax],dw[nmax];
vector<int>a[nmax];
vector<pair<int,int> >g[nmax];
bitset<nmax>viz;
char rs[nmax];
void dfs(int x,int p=-1)
{
	viz[x]=1;
	fin[x]=fup[x]=++tin;
	for(int i=0;i<a[x].size();i++)
	{
		if(a[x][i]==p)continue;
		int y=x^ex[a[x][i]]^ey[a[x][i]];
		if(viz[y])
		{
			fup[x]=min(fup[x],fin[y]);
		}
		else
		{
			dfs(y,a[x][i]);
			fup[x]=min(fup[x],fup[y]);
			if(fup[y]>fin[x])
			{
				br[a[x][i]]=1;
			}
		}
	}
}
void col(int x)
{
	viz[x]=1;
	c[x]=k;
	for(int i=0;i<a[x].size();i++)
	{
		int y=x^ex[a[x][i]]^ey[a[x][i]];
		if(viz[y] || br[a[x][i]])continue;
		col(y);
	}
}
void con(int x)
{
	viz[x]=1;
	for(int i=0;i<a[x].size();i++)
	{
		int y=x^ex[a[x][i]]^ey[a[x][i]];
		if(br[a[x][i]])
		{
			g[c[x]].pb(mkp(c[y],a[x][i]));
			//g[c[y]].pb(c[x]);
			continue;
		}
		if(viz[y])continue;
		con(y);
	}
}
void build(int x,int p)
{
	viz[x]=1;
	par[x][0]=p;
	in[x]=++tin;
	for(int i=1;i<18;i++)par[x][i]=par[par[x][i-1]][i-1];
	for(int i=0;i<g[x].size();i++)
	{
		int y=g[x][i].fr;
		if(y==p)continue;
		build(y,x);
	}
	out[x]=++tin;
}
int anc(int x,int y)
{
	return in[x]<=in[y] && out[y]<=out[x];
}
int lca(int x,int y)
{
	if(anc(x,y))return x;
	if(anc(y,x))return y;
	for(int i=17;i>=0;i--)if(!anc(par[x][i],y))x=par[x][i];
	return par[x][0];
}
void rec(int x,int p,int ed)
{
	viz[x]=1;
	for(int i=0;i<g[x].size();i++)
	{
		int y=g[x][i].fr;
		if(y==p)continue;
		rec(y,x,g[x][i].sc);
		up[x]+=up[y];
		dw[x]+=dw[y];
	}
	//cout<<x<<" "<<ed<<"   "<<up[x]<<" "<<dw[x]<<endl;
	if(up[x])
	{
		if(c[ex[ed]]==x)rs[ed]='R';
		else rs[ed]='L';
	}
	if(dw[x])
	{
		if(c[ex[ed]]==x)rs[ed]='L';
		else rs[ed]='R';
	}
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>ex[i]>>ey[i];
		a[ex[i]].pb(i);
		a[ey[i]].pb(i);
	}
	for(i=1;i<=n;i++)
	{
		if(!viz[i])
		{
			dfs(i);
		}
	}
	viz.reset();
	for(i=1;i<=n;i++)
	{
		if(!viz[i])
		{
			k++;
			col(i);
		}
	}
	viz.reset();
	for(i=1;i<=n;i++)
	{
		if(!viz[i])
		{
			con(i);
		}
	}
	viz.reset();
	for(i=1;i<=k;i++)
	{
		if(viz[i])continue;
		build(i,i);
	}
	cin>>z;
	while(z--)
	{
		cin>>x>>y;
		x=c[x],y=c[y];
		l=lca(x,y);
		up[x]++;
		up[l]--;
		dw[y]++;
		dw[l]--;
	}
	viz.reset();
	for(i=1;i<=k;i++)
	{
		if(viz[i])continue;
		rec(i,i,0);
	}
	for(i=1;i<=m;i++)
	{
		if(rs[i]=='L' || rs[i]=='R')cout<<rs[i];
		else cout<<'B';
	}
	cout<<endl;
	return 0;
}

Compilation message

oneway.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
oneway.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void col(int)':
oneway.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void con(int)':
oneway.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void build(int, int)':
oneway.cpp:83:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void rec(int, int, int)':
oneway.cpp:105:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)
              ~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 7 ms 5240 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 9 ms 5296 KB Output is correct
8 Correct 7 ms 5240 KB Output is correct
9 Correct 7 ms 5112 KB Output is correct
10 Correct 7 ms 5112 KB Output is correct
11 Correct 63 ms 10044 KB Output is correct
12 Correct 71 ms 11416 KB Output is correct
13 Correct 89 ms 13108 KB Output is correct
14 Correct 122 ms 17016 KB Output is correct
15 Correct 124 ms 18296 KB Output is correct
16 Correct 149 ms 25160 KB Output is correct
17 Correct 159 ms 26488 KB Output is correct
18 Correct 163 ms 25208 KB Output is correct
19 Correct 158 ms 27640 KB Output is correct
20 Correct 73 ms 10872 KB Output is correct
21 Correct 65 ms 11384 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 7 ms 5240 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 9 ms 5296 KB Output is correct
8 Correct 7 ms 5240 KB Output is correct
9 Correct 7 ms 5112 KB Output is correct
10 Correct 7 ms 5112 KB Output is correct
11 Correct 63 ms 10044 KB Output is correct
12 Correct 71 ms 11416 KB Output is correct
13 Correct 89 ms 13108 KB Output is correct
14 Correct 122 ms 17016 KB Output is correct
15 Correct 124 ms 18296 KB Output is correct
16 Correct 149 ms 25160 KB Output is correct
17 Correct 159 ms 26488 KB Output is correct
18 Correct 163 ms 25208 KB Output is correct
19 Correct 158 ms 27640 KB Output is correct
20 Correct 73 ms 10872 KB Output is correct
21 Correct 65 ms 11384 KB Output is correct
22 Correct 234 ms 27644 KB Output is correct
23 Correct 216 ms 26120 KB Output is correct
24 Correct 217 ms 26264 KB Output is correct
25 Correct 215 ms 30712 KB Output is correct
26 Correct 223 ms 27388 KB Output is correct
27 Correct 221 ms 26232 KB Output is correct
28 Correct 48 ms 8188 KB Output is correct
29 Correct 99 ms 11872 KB Output is correct
30 Correct 91 ms 12152 KB Output is correct
31 Correct 94 ms 12152 KB Output is correct
32 Correct 126 ms 18416 KB Output is correct