oj.uz

답안 #303154

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
303154 2020-09-19T23:20:04 Z pedroslrey One-Way Streets (CEOI17_oneway) C++17
0 / 100
 5 ms 5248 KB 
#include <bits/stdc++.h>

using namespace std;


struct edge {
	int u, v, id;

	edge(int _u, int _v, int _id) {
		u = _u, v = _v, id = _id;
	}

	int other(int w) {
		return u ^ v ^ w;
	}
};

const int MAXN = 1e5 + 10;
const int MAXK = 30;

vector<edge> graph[MAXN];
int marc[MAXN];
int low[MAXN];
int pre[MAXN];
int pai[MAXN];
int pai2[MAXN];
int comp[MAXN];
vector<edge> ngraph[MAXN];
int dfs_time;
int dp[MAXN][MAXK];
int prof[MAXN];
int cnt[MAXN];

void dfs(int u) {
	marc[u] = 1;
	pre[u] = dfs_time;
	++dfs_time;
	low[u] = 1e9;
	for (edge e: graph[u]) {
		int v = e.other(u);
		if (v == pai[u]) continue;
 
		if (marc[v]) 
			low[u] = min(low[u], pre[v]);
		else {
			pai[v] = u;
			dfs(v);
			low[u] = min(low[u], low[v]);
		}
	}
}

bool bridge(edge e) {
	int u = e.u, v = e.v;
	if (pai[u] != v && pai[v] != u) return false;
	if (u == pai[v]) swap(u, v);
	return low[u] > pre[v];
}

void calc(int u, int c) {
	marc[u] = 1;
	comp[u] = c;
	for (edge e: graph[u]) {
		int v = e.other(u);
		if (marc[v] || bridge(e)) continue;
		calc(v, c);
	}
}

void finish(int u) {
	marc[u] = 1;
	for (edge e: ngraph[u]) {
		int v = e.other(u);
		if (marc[v]) continue;

		pai2[v] = u;
		finish(v);
		cnt[u] += cnt[v];
	}
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);

	vector<edge> edges;
	for (int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);

		edge e(u, v, i);

		graph[u].push_back(e);
		graph[v].push_back(e);
		edges.push_back(e);
	}

	for (int i = 1; i <= n; ++i)
		if (!marc[i]) dfs(i);

	for (int i = 1; i <= n; ++i)
		marc[i] = 0;

	int c = 0;
	for (int i = 1; i <= n; ++i)
		if (!marc[i]) calc(i, ++c);

	for (edge e: edges) 
		if (bridge(e)) {
			edge f(comp[e.u], comp[e.v], -1);
			ngraph[comp[e.u]].push_back(f);
			ngraph[comp[e.v]].push_back(f);
		}

	int p;
	scanf("%d", &p);
	for (int i = 0; i < p; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);

		++cnt[comp[u]];
		--cnt[comp[v]];
	}

	for (int i = 1; i <= n; ++i)
		marc[i] = 0;

	for (int i = 1; i <= c; ++i)
		if (!marc[i]) finish(i);

	for (edge e: edges) {
		int u = comp[e.u], v = comp[e.v];

		bool swaped = false;
		if (u == pai2[v]) {
			swap(u, v);
			swaped = true;
		}
		if (!bridge(e) || cnt[u] == 0) printf("B");
		else if (cnt[u] > 0 && !swaped) printf("R");
		else if (cnt[u] > 0 && swaped) printf("L");
		else if (swaped) printf("R");
		else printf("L");
	}
	printf("\n");
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |  scanf("%d", &p);
      |  ~~~~~^~~~~~~~~~
oneway.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 4 ms 5184 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Incorrect 5 ms 5120 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 4 ms 5184 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Incorrect 5 ms 5120 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 4 ms 5184 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Incorrect 5 ms 5120 KB Output isn't correct
10 Halted 0 ms 0 KB -