oj.uz

Submission #659556

# Submission time Handle Problem Language Result Execution time Memory
659556 2022-11-18T13:45:06 Z jiahng One-Way Streets (CEOI17_oneway) C++14
100 / 100
 274 ms 41548 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ll int
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MOD 1000000007
#define maxn 100010
#define INF (ll)1e18

int TC;
int N,M;
vi adj[maxn];

int low[maxn], disc[maxn], grp[maxn], num = 1;
stack <int> s; bool onstack[maxn]; //disc is discovery time
int ans[maxn], counter = 1;
void dfs(int x, int p) {
	disc[x] = low[x] = counter++;
	s.push(x);
	onstack[x] = true; int co = 0;
	for (auto i: adj[x]) {
		if (i == p){
			co++;
			if (co > 1){
				low[x] = min(low[x],disc[i]);
			}
			continue;
		}
		if (disc[i] == -1) {
			dfs(i,x);
			low[x] = min(low[x],low[i]);
		} else if (onstack[i]) {
			low[x] = min(low[x],disc[i]);
		}
	}
	if (disc[x] == low[x]) {
		int cur;
		while (1) {
			cur = s.top();
			s.pop();
			onstack[cur] = false;
			grp[cur] = num;
			if (cur == x) break;
		}
		num++;
	}
}

int P, X[maxn], Y[maxn];
vpi Z[maxn];

unordered_set <int> st[maxn];
void insert(int i, int x,int y){
	int a = x + y*P, b = x + (!y) * P;
	if (st[i].find(b) != st[i].end()){
		st[i].erase(b); //co[!y]--;
	}else{
		st[i].insert(a); //co[y]++;
	}
}
int ans2[maxn], par[maxn];
bool vis[maxn];
void findans(int x, int p){ //set merging
	int mx = -1; par[x] = p;
	assert(!vis[x]);
	vis[x] = 1;
	aFOR(i,adj[x]) if (i != p){
		findans(i, x);
		if (mx == -1 || st[mx].size() < st[i].size()) mx = i;
	}

	if (mx != -1) st[x].swap(st[mx]);
	aFOR(i,Z[x]) insert(x, i.f, i.s);
	aFOR(i,adj[x]) if (i != p && i != mx){
		aFOR(j, st[i]){
			int z = j; bool y = 0;
			if (j > P){z -= P; y = 1;}
			insert(x, z, y);
		}
		st[i].clear();
	}
	//~ assert(st[x].co[0] == 0 || st[x].co[1] == 0);
	if (st[x].empty()) ans2[x] = 2;
	else if (*st[x].begin() <= P) ans2[x] = 0; // upward
	else ans2[x] = 1; // downward
	//~ else 
	//~ else assert(0);
}
int32_t main() {
    fast;
    mem(ans,-1);
    cin >> N >> M;
    vpi edges;
    int a,b;
    FOR(i,1,M){
		cin >> a >> b; adj[a].pb(b); adj[b].pb(a);
		edges.pb(pi(a,b));
	}
	cin >> P;
	FOR(i,1,P){
		cin >> X[i] >> Y[i];
	}
	
	mem(disc,-1);
	FOR(i,1,N) if (disc[i] == -1) dfs(i,-1);
	
	FOR(i,1,N) adj[i].clear();
	//~ FOR(i,1,N) cout << grp[i] << ' ';
	//~ cout << '\n';
	FOR(i,1,N) vis[i] = 0;
	FOR(i,0,M-1){
		if (grp[edges[i].f] == grp[edges[i].s]){
			ans[i] = 2;
		}else{
			adj[grp[edges[i].f]].pb(grp[edges[i].s]);
			adj[grp[edges[i].s]].pb(grp[edges[i].f]);
		}
	}
	FOR(i,1,P){
		int a = grp[X[i]], b = grp[Y[i]];
		if (a != b){
			Z[a].pb(pi(i, 0)); Z[b].pb(pi(i, 1));
		}
	}
	mem(ans2,-1);
	findans(1,-1);

	FOR(i,1,num-1) if (!vis[i]) findans(i,-1);
	FOR(i,0,M-1){
		int a = grp[edges[i].f], b = grp[edges[i].s];
		if (a != b){
			int x;
			if (par[a] == b) x = a;
			else x = b;
			assert(ans2[x] != -1);
			if (ans2[x] == 2) ans[i] = 2;
			else if (ans2[x] == 0){
				if (x == a){ // a is child, a->b 
					ans[i] = 1;
				}else ans[i] = 0;
			}else{
				if (x == a) ans[i] = 0;
				else ans[i] = 1;
			}
		}
	}
	FOR(i,0,M-1){
		if (ans[i] == 2) cout << 'B';
		else if (ans[i] == 0) cout << 'L';
		else cout << 'R';
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11604 KB Output is correct
2 Correct 7 ms 11684 KB Output is correct
3 Correct 10 ms 11732 KB Output is correct
4 Correct 8 ms 11732 KB Output is correct
5 Correct 7 ms 11820 KB Output is correct
6 Correct 7 ms 11732 KB Output is correct
7 Correct 7 ms 11732 KB Output is correct
8 Correct 7 ms 11692 KB Output is correct
9 Correct 7 ms 11732 KB Output is correct
10 Correct 7 ms 11732 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11604 KB Output is correct
2 Correct 7 ms 11684 KB Output is correct
3 Correct 10 ms 11732 KB Output is correct
4 Correct 8 ms 11732 KB Output is correct
5 Correct 7 ms 11820 KB Output is correct
6 Correct 7 ms 11732 KB Output is correct
7 Correct 7 ms 11732 KB Output is correct
8 Correct 7 ms 11692 KB Output is correct
9 Correct 7 ms 11732 KB Output is correct
10 Correct 7 ms 11732 KB Output is correct
11 Correct 36 ms 16792 KB Output is correct
12 Correct 41 ms 18044 KB Output is correct
13 Correct 54 ms 19288 KB Output is correct
14 Correct 55 ms 20120 KB Output is correct
15 Correct 81 ms 20268 KB Output is correct
16 Correct 68 ms 18492 KB Output is correct
17 Correct 75 ms 20800 KB Output is correct
18 Correct 75 ms 18588 KB Output is correct
19 Correct 66 ms 23324 KB Output is correct
20 Correct 45 ms 17856 KB Output is correct
21 Correct 42 ms 17416 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11604 KB Output is correct
2 Correct 7 ms 11684 KB Output is correct
3 Correct 10 ms 11732 KB Output is correct
4 Correct 8 ms 11732 KB Output is correct
5 Correct 7 ms 11820 KB Output is correct
6 Correct 7 ms 11732 KB Output is correct
7 Correct 7 ms 11732 KB Output is correct
8 Correct 7 ms 11692 KB Output is correct
9 Correct 7 ms 11732 KB Output is correct
10 Correct 7 ms 11732 KB Output is correct
11 Correct 36 ms 16792 KB Output is correct
12 Correct 41 ms 18044 KB Output is correct
13 Correct 54 ms 19288 KB Output is correct
14 Correct 55 ms 20120 KB Output is correct
15 Correct 81 ms 20268 KB Output is correct
16 Correct 68 ms 18492 KB Output is correct
17 Correct 75 ms 20800 KB Output is correct
18 Correct 75 ms 18588 KB Output is correct
19 Correct 66 ms 23324 KB Output is correct
20 Correct 45 ms 17856 KB Output is correct
21 Correct 42 ms 17416 KB Output is correct
22 Correct 179 ms 38660 KB Output is correct
23 Correct 274 ms 41548 KB Output is correct
24 Correct 257 ms 40320 KB Output is correct
25 Correct 161 ms 39232 KB Output is correct
26 Correct 176 ms 35400 KB Output is correct
27 Correct 244 ms 36892 KB Output is correct
28 Correct 34 ms 15632 KB Output is correct
29 Correct 78 ms 22792 KB Output is correct
30 Correct 82 ms 23392 KB Output is correct
31 Correct 61 ms 21892 KB Output is correct
32 Correct 102 ms 27136 KB Output is correct