oj.uz

Submission #79330

# Submission time Handle Problem Language Result Execution time Memory
79330 2018-10-12T09:18:16 Z Saboon One-Way Streets (CEOI17_oneway) C++14
100 / 100
 108 ms 48084 KB 
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iomanip>
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
const int mod = 1e9 + 7;

bool visited[maxn], mark[maxn];
int dp[maxn], h[maxn], a[maxn], b[maxn], from[maxm];

vector <pii> g[maxn];

void dfs (int v, int par = -1, int idx = 0) {
	mark[idx] = 1;
	visited[v] = 1;
	dp[v] = h[v];
	for (auto u : g[v]) {
		if (!mark[u.S] and u.F == par)
			dp[v] = min (dp[v], h[v] - 1);
		if (!visited[u.F]) {
			h[u.F] = h[v] + 1;
			dfs (u.F, v, u.S);
			a[v] += a[u.F];
			b[v] += b[u.F];
			dp[v] = min (dp[v], dp[u.F]);
		}
		else if (u.F != par)
			dp[v] = min (dp[v], h[u.F]);
	}
//	cout << v << " " << par << " -> " << dp[v] << " " << h[v] << endl;
	if (par != -1 and dp[v] == h[v]) {
//		cout << v << " = " << a[v] << " * " << b[v] << endl;
		if (a[v] > b[v]) {
//			cout << idx << " -> " << v << " " << par << endl;
			from[idx] = v;
		}
		else if (a[v] < b[v]) {
//			cout << idx << " -> " << par << " " << v << endl;
			from[idx] = par;
		}
	}
}

pii edge[maxm];

int main() {
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int v, u;
		cin >> v >> u;
		g[v].PB ({u, i});
		g[u].PB ({v, i});
		edge[i] = {v, u};
	}
	for (int i = 1; i <= n; i++)
		random_shuffle (g[i].begin(), g[i].end());
	int p;
	cin >> p;
	for (int i = 1; i <= p; i++) {
		int x, y;
		cin >> x >> y;
		a[x] ++;
		b[y] ++;
	}
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			dfs (i);
		}
	}
	for (int i = 1; i <= m; i++) {
		if (from[i] == edge[i].F)
			cout << "R";
		else if (from[i] == edge[i].S)
			cout << "L";
		else
			cout << "B";
	}
	cout << endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2932 KB Output is correct
3 Correct 5 ms 2932 KB Output is correct
4 Correct 4 ms 2932 KB Output is correct
5 Correct 5 ms 2972 KB Output is correct
6 Correct 4 ms 3000 KB Output is correct
7 Correct 5 ms 3064 KB Output is correct
8 Correct 4 ms 3132 KB Output is correct
9 Correct 5 ms 3164 KB Output is correct
10 Correct 4 ms 3176 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2932 KB Output is correct
3 Correct 5 ms 2932 KB Output is correct
4 Correct 4 ms 2932 KB Output is correct
5 Correct 5 ms 2972 KB Output is correct
6 Correct 4 ms 3000 KB Output is correct
7 Correct 5 ms 3064 KB Output is correct
8 Correct 4 ms 3132 KB Output is correct
9 Correct 5 ms 3164 KB Output is correct
10 Correct 4 ms 3176 KB Output is correct
11 Correct 68 ms 9464 KB Output is correct
12 Correct 65 ms 11440 KB Output is correct
13 Correct 77 ms 13780 KB Output is correct
14 Correct 78 ms 15948 KB Output is correct
15 Correct 82 ms 17232 KB Output is correct
16 Correct 78 ms 17232 KB Output is correct
17 Correct 79 ms 19412 KB Output is correct
18 Correct 80 ms 19412 KB Output is correct
19 Correct 78 ms 22872 KB Output is correct
20 Correct 67 ms 22872 KB Output is correct
21 Correct 66 ms 22872 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2932 KB Output is correct
3 Correct 5 ms 2932 KB Output is correct
4 Correct 4 ms 2932 KB Output is correct
5 Correct 5 ms 2972 KB Output is correct
6 Correct 4 ms 3000 KB Output is correct
7 Correct 5 ms 3064 KB Output is correct
8 Correct 4 ms 3132 KB Output is correct
9 Correct 5 ms 3164 KB Output is correct
10 Correct 4 ms 3176 KB Output is correct
11 Correct 68 ms 9464 KB Output is correct
12 Correct 65 ms 11440 KB Output is correct
13 Correct 77 ms 13780 KB Output is correct
14 Correct 78 ms 15948 KB Output is correct
15 Correct 82 ms 17232 KB Output is correct
16 Correct 78 ms 17232 KB Output is correct
17 Correct 79 ms 19412 KB Output is correct
18 Correct 80 ms 19412 KB Output is correct
19 Correct 78 ms 22872 KB Output is correct
20 Correct 67 ms 22872 KB Output is correct
21 Correct 66 ms 22872 KB Output is correct
22 Correct 100 ms 26236 KB Output is correct
23 Correct 108 ms 26948 KB Output is correct
24 Correct 102 ms 29388 KB Output is correct
25 Correct 107 ms 36192 KB Output is correct
26 Correct 98 ms 36192 KB Output is correct
27 Correct 101 ms 36308 KB Output is correct
28 Correct 55 ms 36308 KB Output is correct
29 Correct 91 ms 38988 KB Output is correct
30 Correct 91 ms 41248 KB Output is correct
31 Correct 91 ms 43632 KB Output is correct
32 Correct 93 ms 48084 KB Output is correct