제출 #103707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103707		E869120	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	838 ms	62036 KiB

oneway

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40