제출 #79330

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

oneway

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