oj.uz

Submission #103707

# Submission time Handle Problem Language Result Execution time Memory
103707 2019-04-02T07:07:38 Z E869120 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 838 ms 62036 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#pragma warning (disable: 4996)

int N, M, A[1 << 18], B[1 << 18], pre[1 << 18], low[1 << 18], col[1 << 18], dp[1 << 17][22], dist[1 << 17], cnt[1 << 17], state[1 << 17], cnts;
map<pair<int, int>, int>Map, Map2;
vector<int>X[1 << 17], Y[1 << 17], Z[1 << 17];
bool bridge[1 << 18], dir[1 << 18], used[1 << 18];

void dfs1(int pos, int prev_) {
	cnts++; pre[pos] = cnts; low[pos] = cnts;

	for (int i = 0; i < X[pos].size(); i++) {
		if (pre[X[pos][i]] >= 1) {
			if (X[pos][i] != prev_) low[pos] = min(low[pos], low[X[pos][i]]);
			continue;
		}
		else {
			dfs1(X[pos][i], pos);
			low[pos] = min(low[pos], low[X[pos][i]]);
			if (low[X[pos][i]] == pre[X[pos][i]]) {
				bridge[abs(Map[make_pair(pos, X[pos][i])])] = true;
			}
		}
	}
}

void dfs2(int pos) {
	if (col[pos] >= 1) return;
	col[pos] = cnts;
	for (int i = 0; i < Y[pos].size(); i++) {
		dfs2(Y[pos][i]);
	}
}

void dfs3(int pos, int dep) {
	used[pos] = true; dist[pos] = dep;
	for (int i = 0; i < Z[pos].size(); i++) {
		if (used[Z[pos][i]] == true) continue;
		dp[Z[pos][i]][0] = pos;
		dfs3(Z[pos][i], dep + 1);
	}
}

int prevs(int pos, int x) {
	for (int i = 21; i >= 0; i--) {
		if (x >= (1 << i)) { pos = dp[pos][i]; x -= (1 << i); }
	}
	return pos;
}

int lca(int u, int v) {
	if (dist[u] > dist[v]) swap(u, v);
	v = prevs(v, dist[v] - dist[u]);
	if (u == v) return u;

	for (int i = 21; i >= 0; i--) {
		if (dp[u][i] != dp[v][i]) {
			u = dp[u][i];
			v = dp[v][i];
		}
	}
	return dp[u][0];
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%d%d", &A[i], &B[i]);
		X[A[i]].push_back(B[i]); Map[make_pair(A[i], B[i])] = i;
		X[B[i]].push_back(A[i]); Map[make_pair(B[i], A[i])] = -i;
	}
	for (int i = 1; i <= N; i++) { pre[i] = 0; low[i] = (1 << 30); }
	for (int i = 1; i <= N; i++) {
		if (pre[i] >= 1) continue;
		dfs1(i, -1);
	}
	for (int i = 1; i <= M; i++) {
		if (bridge[i] == true) continue;
		Y[A[i]].push_back(B[i]);
		Y[B[i]].push_back(A[i]);
	}
	cnts = 0;
	for (int i = 1; i <= N; i++) {
		if (col[i] >= 1) continue;
		cnts++; dfs2(i);
	}
	for (int i = 1; i <= M; i++) {
		if (bridge[i] == false) continue;
		Z[col[A[i]]].push_back(col[B[i]]); Map2[make_pair(col[A[i]], col[B[i]])] = i;
		Z[col[B[i]]].push_back(col[A[i]]); Map2[make_pair(col[B[i]], col[A[i]])] = -i;
	}
	for (int i = 1; i <= N; i++) {
		if (used[i] == true) continue;
		dfs3(i, 0);
	}
	for (int i = 0; i < 21; i++) {
		for (int j = 1; j <= cnts; j++) dp[j][i + 1] = dp[dp[j][i]][i];
	}

	int Q; scanf("%d", &Q);
	for (int i = 1; i <= Q; i++) {
		int ca, cb; scanf("%d%d", &ca, &cb);
		ca = col[ca]; cb = col[cb];
		int v = lca(ca, cb);
		cnt[ca]++; cnt[cb]--;
	}

	vector<pair<int, int>>I;
	for (int i = 1; i <= cnts; i++) I.push_back(make_pair(dist[i], i));
	sort(I.begin(), I.end());

	for (int i = I.size() - 1; i >= 0; i--) {
		cnt[dp[I[i].second][0]] += cnt[I[i].second];
	}

	for (int i = 1; i <= cnts; i++) {
		if (cnt[i] == 0 || dist[i] == 0) continue;
		bool p1 = false; if (Map2[make_pair(i, dp[i][0])] <= -1) p1 = true;
		bool p2 = false; if (cnt[i] <= -1) p2 = true;
		if ((p1^p2) == false) state[abs(Map2[make_pair(i, dp[i][0])])] = 1;
		else state[abs(Map2[make_pair(i, dp[i][0])])] = 2;
	}
	for (int i = 1; i <= M; i++) {
		if (state[i] == 0) printf("B");
		if (state[i] == 1) printf("R");
		if (state[i] == 2) printf("L");
	}
	printf("\n");
	return 0;
}

Compilation message

oneway.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
oneway.cpp: In function 'void dfs1(int, int)':
oneway.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int)':
oneway.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Y[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs3(int, int)':
oneway.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Z[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:108:7: warning: unused variable 'v' [-Wunused-variable]
   int v = lca(ca, cb);
       ^
oneway.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int Q; scanf("%d", &Q);
         ~~~~~^~~~~~~~~~
oneway.cpp:106:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int ca, cb; scanf("%d%d", &ca, &cb);
               ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9600 KB Output is correct
2 Correct 10 ms 9600 KB Output is correct
3 Correct 11 ms 9856 KB Output is correct
4 Correct 13 ms 10112 KB Output is correct
5 Correct 13 ms 10112 KB Output is correct
6 Correct 12 ms 9856 KB Output is correct
7 Correct 13 ms 10112 KB Output is correct
8 Correct 13 ms 10112 KB Output is correct
9 Correct 11 ms 9856 KB Output is correct
10 Correct 13 ms 9856 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9600 KB Output is correct
2 Correct 10 ms 9600 KB Output is correct
3 Correct 11 ms 9856 KB Output is correct
4 Correct 13 ms 10112 KB Output is correct
5 Correct 13 ms 10112 KB Output is correct
6 Correct 12 ms 9856 KB Output is correct
7 Correct 13 ms 10112 KB Output is correct
8 Correct 13 ms 10112 KB Output is correct
9 Correct 11 ms 9856 KB Output is correct
10 Correct 13 ms 9856 KB Output is correct
11 Correct 308 ms 29364 KB Output is correct
12 Correct 306 ms 30600 KB Output is correct
13 Correct 379 ms 33016 KB Output is correct
14 Correct 452 ms 39008 KB Output is correct
15 Correct 461 ms 41712 KB Output is correct
16 Correct 726 ms 55144 KB Output is correct
17 Correct 624 ms 57196 KB Output is correct
18 Correct 739 ms 55312 KB Output is correct
19 Correct 588 ms 58736 KB Output is correct
20 Correct 276 ms 30456 KB Output is correct
21 Correct 225 ms 30200 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9600 KB Output is correct
2 Correct 10 ms 9600 KB Output is correct
3 Correct 11 ms 9856 KB Output is correct
4 Correct 13 ms 10112 KB Output is correct
5 Correct 13 ms 10112 KB Output is correct
6 Correct 12 ms 9856 KB Output is correct
7 Correct 13 ms 10112 KB Output is correct
8 Correct 13 ms 10112 KB Output is correct
9 Correct 11 ms 9856 KB Output is correct
10 Correct 13 ms 9856 KB Output is correct
11 Correct 308 ms 29364 KB Output is correct
12 Correct 306 ms 30600 KB Output is correct
13 Correct 379 ms 33016 KB Output is correct
14 Correct 452 ms 39008 KB Output is correct
15 Correct 461 ms 41712 KB Output is correct
16 Correct 726 ms 55144 KB Output is correct
17 Correct 624 ms 57196 KB Output is correct
18 Correct 739 ms 55312 KB Output is correct
19 Correct 588 ms 58736 KB Output is correct
20 Correct 276 ms 30456 KB Output is correct
21 Correct 225 ms 30200 KB Output is correct
22 Correct 670 ms 58328 KB Output is correct
23 Correct 703 ms 56484 KB Output is correct
24 Correct 838 ms 56684 KB Output is correct
25 Correct 649 ms 62036 KB Output is correct
26 Correct 697 ms 57832 KB Output is correct
27 Correct 741 ms 56552 KB Output is correct
28 Correct 98 ms 14328 KB Output is correct
29 Correct 323 ms 31196 KB Output is correct
30 Correct 286 ms 31444 KB Output is correct
31 Correct 342 ms 31736 KB Output is correct
32 Correct 390 ms 39712 KB Output is correct