oj.uz

Submission #695609

# Submission time Handle Problem Language Result Execution time Memory
695609 2023-02-05T06:53:05 Z KiaRez One-Way Streets (CEOI17_oneway) C++17
100 / 100
 262 ms 27552 KB 
/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;

#define SQ									   350
#define endl                                   '\n'
#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define PQ                                     priority_queue
#define size(x)                                ((ll)x.size())
#define DASH                                   "---------"
#define UNDERLINE                              "_________"
#define all(x)                                 (x).begin(),(x).end()
#define FORD(i, s, e)                          for(int i=s; i>=e; --i)
#define FOR(i, s, e)                           for(int i=s; i<=e; ++i)
#define kill(x)		                           cout << x << '\n', exit(0);
#define set_dec(x)	                           cout << fixed << setprecision(x);
#define ios				                       ios_base::sync_with_stdio(false), cin.tie(0)
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define file_io(x,y)	                       freopen(x, "r", stdin); freopen(y, "w", stdout);

const int _N = 232323, _LG=131072, _lg=18;
const ll _MOD = 1e9+7; // 998244353

ll getmod(ll a, ll mod=_MOD)                   {return (a+3*mod)%mod;}
ll max(ll a, ll b)                             {return (a>b ? a : b);}
ll min(ll a, ll b)                             {return (a<b ? a : b);}
ll abso(ll a)                                  {return (a<0?-a:a);}

int n, m, p, pref[_N][2], par[_N][_lg], low[_N], h[_N], mark[_N], ANS[_N];
vector<pii> adj[_N];
pii E[_N];

void addEdge(int ind) {
	int v,u;
	cin>>v>>u;
	adj[v].pb({u, ind});
	adj[u].pb({v, ind});
	E[ind]={v, u};
}

void dfs(int v=1, int ind=0) {
	low[v]=1e9, mark[v]=1;
	FOR(i,1,_lg-1) {par[v][i]=par[par[v][i-1]][i-1];}
	for(auto it2 : adj[v]) {
		auto it = it2.F;
		if(mark[it]==0) {
			par[it][0]=v, h[it]=h[v]+1;
			dfs(it, it2.S);
			low[v]=min(low[it], low[v]);
		} else if (it2.S!=ind) {
			low[v]=min(h[it], low[v]);
		}
	}
}

int getPar(int v, int dist) {
	while(dist>0) {
		v=par[v][(int)log2(dist&-dist)];
		dist-=(dist&-dist);
	}
	return v;
}
 
int getLCA(int v, int u) {
	if(h[v]>h[u]) {swap(v,u);}
	u=getPar(u, h[u]-h[v]);
	if(v==u) {return v;}
	FORD(i,_lg-1, 0) {
		if(par[v][i]!=par[u][i]) {v=par[v][i], u=par[u][i];}
	}
	return par[v][0];
}

void partial(int v=1) {
	mark[v]=1;
	for(auto it : adj[v]) {
		if(!mark[it.F]) {
			partial(it.F);
			pref[v][0]+=pref[it.F][0];
			pref[v][1]+=pref[it.F][1];
			if (low[it.F]>h[v] && (pref[it.F][0]!=0||pref[it.F][1]!=0)) {
				ANS[it.S] = (pref[it.F][0]!=0 ? (E[it.S].F==it.F ? 1 : -1) : (E[it.S].F==v ? 1 : -1));
			}
		}
	}
}

int main () {
	ios;

	// file_io("oneway.01.01.in", "out.txt");

	cin>>n>>m; h[1]=1;
	FOR(i,1,m) {addEdge(i);}
	FOR(i,1,n) {
		if(!mark[i]) {
			dfs(i, 0);
		}
	}
	fill(mark, mark+n+2, 0);
	cin>>p;
	FOR(i,1,p) {
		int v,u,lca;
		cin>>v>>u; // 0 -> up | 1 -> down
		lca=getLCA(v,u);
		if (lca==v) {
			pref[u][1]++;pref[v][1]--;
		} else if (lca==u) {
			pref[v][0]++;pref[u][0]--;
		} else {
			pref[v][0]++;pref[u][1]++;pref[lca][0]--;pref[lca][1]--;
		}
	}
	FOR(i,1,n) {
		if(!mark[i]) {
			partial(i);
		}
	}

	// FOR(i,1,n) {
	// 	cout<<par[i][0]<<' ';
	// }
	// cout<<endl;

	FOR(i,1,m) {
		cout<<(ANS[i]==0 ? 'B' : (ANS[i]==1 ? 'R' : 'L'));
	}

	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5796 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 5 ms 5844 KB Output is correct
4 Correct 4 ms 5972 KB Output is correct
5 Correct 4 ms 5972 KB Output is correct
6 Correct 4 ms 5844 KB Output is correct
7 Correct 4 ms 5972 KB Output is correct
8 Correct 6 ms 5924 KB Output is correct
9 Correct 6 ms 5976 KB Output is correct
10 Correct 5 ms 5924 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5796 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 5 ms 5844 KB Output is correct
4 Correct 4 ms 5972 KB Output is correct
5 Correct 4 ms 5972 KB Output is correct
6 Correct 4 ms 5844 KB Output is correct
7 Correct 4 ms 5972 KB Output is correct
8 Correct 6 ms 5924 KB Output is correct
9 Correct 6 ms 5976 KB Output is correct
10 Correct 5 ms 5924 KB Output is correct
11 Correct 80 ms 13520 KB Output is correct
12 Correct 102 ms 15496 KB Output is correct
13 Correct 107 ms 18228 KB Output is correct
14 Correct 140 ms 21448 KB Output is correct
15 Correct 148 ms 22304 KB Output is correct
16 Correct 125 ms 20640 KB Output is correct
17 Correct 116 ms 22820 KB Output is correct
18 Correct 109 ms 20836 KB Output is correct
19 Correct 102 ms 24188 KB Output is correct
20 Correct 70 ms 16620 KB Output is correct
21 Correct 61 ms 16552 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5796 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 5 ms 5844 KB Output is correct
4 Correct 4 ms 5972 KB Output is correct
5 Correct 4 ms 5972 KB Output is correct
6 Correct 4 ms 5844 KB Output is correct
7 Correct 4 ms 5972 KB Output is correct
8 Correct 6 ms 5924 KB Output is correct
9 Correct 6 ms 5976 KB Output is correct
10 Correct 5 ms 5924 KB Output is correct
11 Correct 80 ms 13520 KB Output is correct
12 Correct 102 ms 15496 KB Output is correct
13 Correct 107 ms 18228 KB Output is correct
14 Correct 140 ms 21448 KB Output is correct
15 Correct 148 ms 22304 KB Output is correct
16 Correct 125 ms 20640 KB Output is correct
17 Correct 116 ms 22820 KB Output is correct
18 Correct 109 ms 20836 KB Output is correct
19 Correct 102 ms 24188 KB Output is correct
20 Correct 70 ms 16620 KB Output is correct
21 Correct 61 ms 16552 KB Output is correct
22 Correct 195 ms 23928 KB Output is correct
23 Correct 228 ms 21964 KB Output is correct
24 Correct 229 ms 22120 KB Output is correct
25 Correct 262 ms 27552 KB Output is correct
26 Correct 261 ms 23444 KB Output is correct
27 Correct 192 ms 22064 KB Output is correct
28 Correct 60 ms 9892 KB Output is correct
29 Correct 152 ms 17228 KB Output is correct
30 Correct 128 ms 17548 KB Output is correct
31 Correct 149 ms 17732 KB Output is correct
32 Correct 166 ms 21452 KB Output is correct