oj.uz

Submission #161590

# Submission time Handle Problem Language Result Execution time Memory
161590 2019-11-03T08:11:15 Z shayan_p One-Way Streets (CEOI17_oneway) C++14
100 / 100
 330 ms 26732 KB 
// Remember...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1e5+10,mod=1e9+7;
const ll inf=1e18;

vector<pii> v[maxn], g[maxn];
int C, h[maxn], hh[maxn];
bool mark[maxn];

int ans[maxn], who[maxn];

void prep(int u,int par=-1){
    mark[u]=1;
    hh[u]= h[u];
    for(auto p:v[u]){
	if(p.S!=par){
	    if(mark[p.F])
		hh[u]=min(hh[u], h[p.F]);
	    else
		h[p.F]= h[u]+1, prep(p.F,p.S), hh[u]=min(hh[u], hh[p.F]);
	}
    }
}
void buildg(int u,int id){
    who[u]=id;
    mark[u]=1;
    for(auto p:v[u]){
	if(mark[p.F]==0){
	    if(hh[p.F]==h[p.F])
		g[id].PB({++C,p.S}), buildg(p.F,C);
	    else
		buildg(p.F,id);
	}
    }
}

int sp[20][maxn];
int h2[maxn];

int cntd[maxn], cntu[maxn];

void prep2(int u,int par=0){
    mark[u]=1;
    h2[u]= h2[par]+1;
    sp[0][u]= par;
    for(int i=1;i<20;i++)
	sp[i][u]= sp[i-1][sp[i-1][u]];
    for(auto p:g[u])
	prep2(p.F,u);
}
int lca(int a,int b){
    if(h2[a]<h2[b]) swap(a,b);
    for(int i=19;i>=0;i--)
	if(h2[sp[i][a]]>=h2[b]) a=sp[i][a];
    if(a==b) return a;
    for(int i=19;i>=0;i--)
	if(sp[i][a]!=sp[i][b]) a=sp[i][a], b=sp[i][b];
    return sp[0][a];
}

void dfs(int u,int par=-1){
    mark[u]=1;
    for(auto p:g[u]){
	dfs(p.F,p.S);
	cntu[u]+= cntu[p.F];
	cntd[u]+= cntd[p.F];
    }
    assert((cntu[u] && cntd[u])==0);
    if(cntu[u])
	ans[par]=1;
    if(cntd[u])
	ans[par]=0;
}

vector<pii> ed;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    memset(ans,-1,sizeof ans);
    
    int n,m; cin>>n>>m;

    for(int i=0;i<m;i++){
	int a,b; cin>>a>>b;
	v[a].PB({b,i});
	v[b].PB({a,i});
	ed.PB({a,b});
    }
    for(int i=1;i<=n;i++)
	if(mark[i]==0)
	    prep(i);
    memset(mark,0,sizeof mark);
    for(int i=1;i<=n;i++)
	if(mark[i]==0)
	    buildg(i,++C);

    memset(mark,0,sizeof mark);
    for(int i=1;i<=C;i++)
	if(mark[i]==0)
	    prep2(i);
    
    int q; cin>>q;
    for(int i=0;i<q;i++){
	int a,b; cin>>a>>b;
	a=who[a], b=who[b];
	int lc=lca(a,b);
	cntu[a]++, cntu[lc]--;
	cntd[b]++, cntd[lc]--;
    }

    memset(mark,0,sizeof mark);
    for(int i=1;i<=C;i++)
	if(mark[i]==0)
	    dfs(i);

    for(int i=0;i<m;i++){
	if(ans[i]==-1) cout<<'B';
	else if((ans[i]) ^ (h[ed[i].F] > h[ed[i].S])) cout<<'L';
	else cout<<'R';
    }
    return cout<<endl,0;
}
// Deathly mistakes:
//  * Read the problem carefully.
//  * Check maxn.
//  * Overflows.


// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5624 KB Output is correct
2 Correct 7 ms 5624 KB Output is correct
3 Correct 8 ms 5752 KB Output is correct
4 Correct 8 ms 5752 KB Output is correct
5 Correct 7 ms 5852 KB Output is correct
6 Correct 7 ms 5752 KB Output is correct
7 Correct 8 ms 5880 KB Output is correct
8 Correct 8 ms 5852 KB Output is correct
9 Correct 7 ms 5752 KB Output is correct
10 Correct 7 ms 5752 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5624 KB Output is correct
2 Correct 7 ms 5624 KB Output is correct
3 Correct 8 ms 5752 KB Output is correct
4 Correct 8 ms 5752 KB Output is correct
5 Correct 7 ms 5852 KB Output is correct
6 Correct 7 ms 5752 KB Output is correct
7 Correct 8 ms 5880 KB Output is correct
8 Correct 8 ms 5852 KB Output is correct
9 Correct 7 ms 5752 KB Output is correct
10 Correct 7 ms 5752 KB Output is correct
11 Correct 58 ms 10828 KB Output is correct
12 Correct 67 ms 11704 KB Output is correct
13 Correct 69 ms 13036 KB Output is correct
14 Correct 90 ms 15976 KB Output is correct
15 Correct 86 ms 17132 KB Output is correct
16 Correct 107 ms 22608 KB Output is correct
17 Correct 112 ms 24224 KB Output is correct
18 Correct 120 ms 22624 KB Output is correct
19 Correct 118 ms 25064 KB Output is correct
20 Correct 64 ms 11240 KB Output is correct
21 Correct 62 ms 11116 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5624 KB Output is correct
2 Correct 7 ms 5624 KB Output is correct
3 Correct 8 ms 5752 KB Output is correct
4 Correct 8 ms 5752 KB Output is correct
5 Correct 7 ms 5852 KB Output is correct
6 Correct 7 ms 5752 KB Output is correct
7 Correct 8 ms 5880 KB Output is correct
8 Correct 8 ms 5852 KB Output is correct
9 Correct 7 ms 5752 KB Output is correct
10 Correct 7 ms 5752 KB Output is correct
11 Correct 58 ms 10828 KB Output is correct
12 Correct 67 ms 11704 KB Output is correct
13 Correct 69 ms 13036 KB Output is correct
14 Correct 90 ms 15976 KB Output is correct
15 Correct 86 ms 17132 KB Output is correct
16 Correct 107 ms 22608 KB Output is correct
17 Correct 112 ms 24224 KB Output is correct
18 Correct 120 ms 22624 KB Output is correct
19 Correct 118 ms 25064 KB Output is correct
20 Correct 64 ms 11240 KB Output is correct
21 Correct 62 ms 11116 KB Output is correct
22 Correct 330 ms 24176 KB Output is correct
23 Correct 294 ms 22764 KB Output is correct
24 Correct 309 ms 22720 KB Output is correct
25 Correct 306 ms 26732 KB Output is correct
26 Correct 266 ms 23784 KB Output is correct
27 Correct 262 ms 22968 KB Output is correct
28 Correct 61 ms 8936 KB Output is correct
29 Correct 104 ms 10984 KB Output is correct
30 Correct 106 ms 11116 KB Output is correct
31 Correct 101 ms 11372 KB Output is correct
32 Correct 184 ms 16628 KB Output is correct