Submission #1005122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005122		vqpahmad	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	92 ms	23896 KiB

oneway

#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e5 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
vector<pii> adj[MAXN];
int id[MAXN], fa[MAXN][20];
int dep[MAXN];
int dir[2][MAXN];
bool vis[MAXN];
void dfs1(int node, int par){
	debug(node, par);
	vis[node] = 1;
	fa[node][0] = par;
	dep[node] = dep[par] + 1;
	for (int b = 1; b < 20; b++){
		fa[node][b] = fa[fa[node][b - 1]][b - 1];
	}
	for (auto [to, idx] : adj[node]){
		if (idx == id[node]) continue;
		if (vis[to]) {
			if (dep[to] < dep[node]){
				debug(node, to, par, "!");
				dir[0][node] += 1;
				dir[0][to] -= 1;
				dir[1][node] += 1;
				dir[1][to] -= 1;
			}
		}
		else {
			id[to] = idx;
			dfs1(to, node);
		}
	}
}

void dfs3(int node){
	vis[node] = 1;
	for (auto [to, idx] : adj[node]){
		if (vis[to]) continue;
		dfs3(to);
		dir[0][node] += dir[0][to];
		dir[1][node] += dir[1][to];
	}
}
int LCA(int u, int v){
	if (dep[u] > dep[v]) swap(u, v);
	for (int b = 19; b >= 0; b--){
		if (dep[fa[v][b]] >= dep[u]) v = fa[v][b];
	}
	if (u == v) return u;
	for (int b = 19; b >= 0; b--){
		if (fa[u][b] != fa[v][b]){
			u = fa[u][b];
			v = fa[v][b];
		}
	}
	return fa[u][0];
}
int ans[MAXN];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	vector<pii> edges(m + 1);
	for (int i = 0; i < m; i++){
		int u, v;
		cin >> u >> v;
		edges[i + 1] = {u, v};
		adj[u].pb({v, i + 1});
		adj[v].pb({u, i + 1});
	}
	for (int i = 1; i <= n; i++){
		if (!vis[i]){
			dfs1(i, i);
		}
	}
	for (int i = 0; i <= n; i++){
		debug(i, dir[0][i], dir[1][i]);
	}
	debug("E");
	int q;
	cin >> q;
	while (q--){
		int u, v;
		cin >> u >> v;
		int lca = LCA(u, v);
		dir[0][u] += 1;
		dir[0][lca] -= 1;
		dir[1][v] += 1;
		dir[1][lca] -= 1;
		debug(u, v, lca);
		// u -> lca up 
		// v -> lca down
	}
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++){
		if (!vis[i]){
			dfs3(i);
		}
	}
	memset(ans, -1, sizeof(ans));
	for (int i = 2; i <= n; i++){
		debug(i, dir[0][i], dir[1][i]);
		if ((!!dir[0][i])^(!!dir[1][i])){
			if (dir[1][i]){
				ans[id[i]] = (edges[id[i]].F == fa[i][0]);
			}
			if (dir[0][i]){
				ans[id[i]] = (edges[id[i]].F == i);
			}
		}
	}
	for (int i = 1; i <= m; i++){
		if (ans[i] == -1){
			cout << 'B';
		} else if (ans[i] == 1) {
			cout << 'R';
		}
		else {
			cout << 'L';
		}
	}
	cout << endl;
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs1(int, int)':
oneway.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
oneway.cpp:29:2: note: in expansion of macro 'debug'
   29 |  debug(node, par);
      |  ^~~~~
oneway.cpp:36:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |  for (auto [to, idx] : adj[node]){
      |            ^
oneway.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
oneway.cpp:40:5: note: in expansion of macro 'debug'
   40 |     debug(node, to, par, "!");
      |     ^~~~~
oneway.cpp: In function 'void dfs3(int)':
oneway.cpp:56:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |  for (auto [to, idx] : adj[node]){
      |            ^
oneway.cpp: In function 'int main()':
oneway.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
oneway.cpp:97:3: note: in expansion of macro 'debug'
   97 |   debug(i, dir[0][i], dir[1][i]);
      |   ^~~~~
oneway.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
oneway.cpp:99:2: note: in expansion of macro 'debug'
   99 |  debug("E");
      |  ^~~~~
oneway.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
oneway.cpp:110:3: note: in expansion of macro 'debug'
  110 |   debug(u, v, lca);
      |   ^~~~~
oneway.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
oneway.cpp:122:3: note: in expansion of macro 'debug'
  122 |   debug(i, dir[0][i], dir[1][i]);
      |   ^~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40