제출 #1323257

#제출 시각아이디문제언어결과실행 시간메모리
1323257blackscreen1One-Way Streets (CEOI17_oneway)C++20
0 / 100
1 ms332 KiB
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, m, t, cv[100005], t1, t2, a[100005];
vector<pll> adj[100005];
pll edge[100005];
bool vis[100005];
ll ma[100005];
vector<ll> rt;
ll dfs(ll nd, ll pr) {
	vis[nd] = 1;
	ll fn = 0;
	for (auto it : adj[nd]) {
		if (it.first == pr) continue;
		if (vis[it.second]) {
			fn++;
			ma[it.first] = 2;
			cv[it.second]++;
			continue;
		}
		fn += dfs(it.second, it.first);
		a[nd] += a[it.second];
	}
	fn -= cv[nd];
	assert(fn >= 0);
	if (pr != -1) {
		if (fn != 0 || a[nd] == 0) ma[pr] = 2;
		else if (a[nd] > 0) ma[pr] = (nd == edge[pr].first ? 0 : 1);
		else ma[pr] = (nd == edge[pr].first ? 1 : 0);
	}
	return fn;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	iloop(0, m) {
		cin >> edge[i].first >> edge[i].second;
		edge[i].first--, edge[i].second--;
		adj[edge[i].first].push_back({i, edge[i].second});
		adj[edge[i].second].push_back({i, edge[i].first});
	}
	cin >> t;
	iloop(0, t) {
		cin >> t1 >> t2;
		t1--, t2--;
		a[t1]++, a[t2]--;
	}
	iloop(0, n) if (!vis[i]) dfs(i, -1);
	string c = "RLB";
	iloop(0, m) cout << c[ma[i]];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...