oj.uz

Submission #43121

# Submission time Handle Problem Language Result Execution time Memory
43121 2018-03-09T09:46:09 Z win11905 One-Way Streets (CEOI17_oneway) C++11
0 / 100
 3000 ms 10060 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int MAXN = 1e5 + 5;

vector<pii> g[MAXN];
int n, m, par[MAXN][18], dep[MAXN], d1[MAXN], d2[MAXN];
char ans[MAXN];
bool chk[MAXN];
pii E[MAXN];

void dfs(int u, int p) {
	dep[u] = dep[p] + 1;
	par[u][0] = p;
	for(int i = 1; i <= 17; ++i) par[u][i] = par[par[u][i-1]][i-1];
	for(auto v : g[u]) if(par[v.x][0] == -1) {
		chk[v.y] = true;
		dfs(v.x, u);
	}
}

int lca(int a, int b) {
	if(dep[a] < dep[b]) swap(a, b);
	for(int i = 17; i >= 0; --i) if(dep[par[a][i]] >= dep[b]) a = par[a][i];
	if(a == b) return a;
	for(int i = 17; i >= 0; --i) if(par[a][i] != par[b][i]) a = par[a][i], b=  par[b][i];
	return par[a][0];
}

void dfs1(int u) {
	for(auto v : g[u]) if(par[v.x][0] == u) {
		dfs1(v.x);
		d1[u] += d1[v.x], d2[u] += d2[v.x];
		ans[v.y] = 'B';
		int node = -1;
		if(d2[v.x] > 0) node = v.x;
		if(d2[v.x] < 0) node = u;
		if(node == -1 || d1[v.x]) continue;
		if(node == E[v.y].x) ans[v.y] = 'R';
		else ans[v.y] = 'L';
	}
}

int main() {
	#ifdef INPUT
	freopen("r", "r", stdin);
	#endif
	memset(par, -1, sizeof par);
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		int u, v; scanf("%d %d", &u, &v);
		g[u].emplace_back(v, i);
		g[v].emplace_back(u, i);
		E[i] = pii(u, v);
	}
	for(int i = 1; i <= n; ++i) if(par[i][0] == -1) dfs(i, 0);
	for(int i = 1; i <= m; ++i) if(!chk[i]) d1[E[i].x]++, d1[E[i].y]++, d1[lca(E[i].x, E[i].y)] -= 2, ans[i] = 'B';
	int t; scanf("%d", &t);
	while(t--) {
		int a, b;
		scanf("%d %d", &a, &b);
		d2[a]++, d2[b]--;
	}
	for(int i = 1; i <= n; ++i) if(!par[i][0]) dfs1(i);
	printf("%s\n", ans+1);
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:52:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
oneway.cpp:54:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d %d", &u, &v);
                                   ^
oneway.cpp:61:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int t; scanf("%d", &t);
                        ^
oneway.cpp:64:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
                         ^

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9720 KB Output is correct
2 Correct 8 ms 9720 KB Output is correct
3 Correct 9 ms 9876 KB Output is correct
4 Correct 9 ms 9876 KB Output is correct
5 Correct 9 ms 9956 KB Output is correct
6 Execution timed out 3018 ms 10060 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9720 KB Output is correct
2 Correct 8 ms 9720 KB Output is correct
3 Correct 9 ms 9876 KB Output is correct
4 Correct 9 ms 9876 KB Output is correct
5 Correct 9 ms 9956 KB Output is correct
6 Execution timed out 3018 ms 10060 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9720 KB Output is correct
2 Correct 8 ms 9720 KB Output is correct
3 Correct 9 ms 9876 KB Output is correct
4 Correct 9 ms 9876 KB Output is correct
5 Correct 9 ms 9956 KB Output is correct
6 Execution timed out 3018 ms 10060 KB Time limit exceeded
7 Halted 0 ms 0 KB -