oj.uz

Submission #657000

# Submission time Handle Problem Language Result Execution time Memory
657000 2022-11-08T17:00:40 Z AmirAli_H1 One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 24644 KB 
// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

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

#define all(x)		(x).begin(),(x).end()
#define len(x)		((ll) (x).size())
#define F		first
#define S		second
#define pb		push_back
#define sep             ' '
#define endl            '\n'
#define Mp		make_pair
#define debug(x)	cerr << #x << ": " <<  x << endl;
#define kill(x)		cout << x << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define file_io(x,y)	freopen(x, "r", stdin); freopen(y, "w", stdout);

int n, m;
const int maxn = 1e5 + 5;
const int maxlg = 20;
vector<pii> adj[maxn];
vector<pii> ques[maxn];
pii edgs[maxn];
vector<int> oedgs, nedgs;
bool mark[maxn];
int h[maxn], mn[maxn];
pii mq[maxn];
int st[maxn], ft[maxn];
int timer = 0;
int up[maxn][maxlg];
int col[maxn]; int c = 0;
char ans[maxn], pre_ans[maxn];
bool done = 0;

void pre_dfs(int v, int i = -1) {
	mark[v] = 1; mn[v] = h[v];
	for (auto f : adj[v]) {
		int u = f.F, j = f.S;
		if (!mark[u]) {
			h[u] = h[v] + 1;
			pre_dfs(u, j);
			mn[v] = min(mn[v], mn[u]);
		}
		else if (j != i) {
			mn[v] = min(mn[v], h[u]);
			oedgs.pb(j);
		}
	}
	if (mn[v] >= h[v] && i != -1) nedgs.pb(i);
	else if (i != -1) oedgs.pb(i);
}

void dfs_col(int v) {
	mark[v] = 1; col[v] = c;
	for (auto f : adj[v]) {
		int u = f.F, j = f.S;
		if (!mark[u]) dfs_col(u);
	}
}

void pre_dfsx(int v, int p = -1) {
	mark[v] = 1;
	st[v] = timer++;
	
	up[v][0] = (p != -1) ? p : v;
	for (int i = 1; i < maxlg; i++) {
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	
	for (auto f : adj[v]) {
		int u = f.F, j = f.S;
		if (!mark[u]) pre_dfsx(u, v);
	}
	ft[v] = timer++;
}

bool is_gr(int u, int v) {
	return (st[u] <= st[v] && ft[u] >= ft[v]);
}

int get_lca(int v, int u) {
	if (is_gr(v, u)) return v;
	if (is_gr(u, v)) return u;
	
	for (int i = maxlg - 1; i >= 0; i--) {
		if (!is_gr(up[u][i], v)) u = up[u][i];
	}
	return up[u][0];
}

void solve_dfs(int v, int x, int i = -1) {
	mark[v] = 1;
	if (v == x) {
		done = 1;
		return ;
	}
	for (auto f : adj[v]) {
		int u = f.F, j = f.S;
		if (!mark[u]) {
			if (v == col[edgs[j].F]) ans[j] = 'R';
			else ans[j] = 'L';
			solve_dfs(u, x, j);
			if (done) return ;
			ans[j] = pre_ans[j];
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v; u--; v--;
		if (u != v) {
			adj[u].pb(Mp(v, i)); adj[v].pb(Mp(u, i));
			edgs[i] = Mp(u, v);
		}
	}
	
	fill(mark, mark + n, 0);
	for (int i = 0; i < n; i++) {
		if (!mark[i]) pre_dfs(i);
	}
	
	for (int i = 0; i < n; i++) adj[i].clear();
	for (int i : oedgs) {
		int u = edgs[i].F, v = edgs[i].S;
		adj[u].pb(Mp(v, i)); adj[v].pb(Mp(u, i));
	}
	
	fill(mark, mark + n, 0);
	for (int i = 0; i < n; i++) {
		if (!mark[i]) {
			dfs_col(i); c++;
		}
	}
	
	for (int i = 0; i < n; i++) adj[i].clear();
	for (int i : nedgs) {
		int u = col[edgs[i].F], v = col[edgs[i].S];
		adj[u].pb(Mp(v, i)); adj[v].pb(Mp(u, i));
	}
	
	fill(mark, mark + n, 0);
	for (int i = 0; i < c; i++) {
		if (!mark[i]) pre_dfsx(i);
	}
	
	fill(ans, ans + m, 'B');
	
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int u, v;
		cin >> u >> v; u--; v--;
		u = col[u]; v = col[v];
		if (u == v) continue;
		fill(mark, mark + n, 0);
		for (int j = 0; j < m; j++) pre_ans[j] = ans[j];
		done = 0; solve_dfs(u, v);
	}
	
	for (int i = 0; i < m; i++) cout << ans[i];
	cout << endl;
	
	return 0;
}

Compilation message

oneway.cpp: In function 'void dfs_col(int)':
oneway.cpp:62:16: warning: unused variable 'j' [-Wunused-variable]
   62 |   int u = f.F, j = f.S;
      |                ^
oneway.cpp: In function 'void pre_dfsx(int, int)':
oneway.cpp:77:16: warning: unused variable 'j' [-Wunused-variable]
   77 |   int u = f.F, j = f.S;
      |                ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5236 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 4 ms 5204 KB Output is correct
7 Correct 4 ms 5204 KB Output is correct
8 Correct 5 ms 5204 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5236 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 4 ms 5204 KB Output is correct
7 Correct 4 ms 5204 KB Output is correct
8 Correct 5 ms 5204 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 52 ms 14248 KB Output is correct
12 Correct 54 ms 15032 KB Output is correct
13 Correct 56 ms 16104 KB Output is correct
14 Correct 92 ms 18368 KB Output is correct
15 Correct 78 ms 19300 KB Output is correct
16 Correct 115 ms 21504 KB Output is correct
17 Correct 411 ms 24060 KB Output is correct
18 Correct 677 ms 21296 KB Output is correct
19 Correct 258 ms 24520 KB Output is correct
20 Correct 51 ms 14140 KB Output is correct
21 Correct 49 ms 13864 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5236 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 4 ms 5204 KB Output is correct
7 Correct 4 ms 5204 KB Output is correct
8 Correct 5 ms 5204 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 52 ms 14248 KB Output is correct
12 Correct 54 ms 15032 KB Output is correct
13 Correct 56 ms 16104 KB Output is correct
14 Correct 92 ms 18368 KB Output is correct
15 Correct 78 ms 19300 KB Output is correct
16 Correct 115 ms 21504 KB Output is correct
17 Correct 411 ms 24060 KB Output is correct
18 Correct 677 ms 21296 KB Output is correct
19 Correct 258 ms 24520 KB Output is correct
20 Correct 51 ms 14140 KB Output is correct
21 Correct 49 ms 13864 KB Output is correct
22 Execution timed out 3057 ms 24644 KB Time limit exceeded
23 Halted 0 ms 0 KB -