Submission #156144

#	Time	Username	Problem	Language	Result	Execution time	Memory
156144		ZwariowanyMarcin	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	6 ms	4984 KiB

oneway

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl;
#define ios cin.tie(0); ios_base::sync_with_stdio(0)
  
using namespace std;				

const int nax = 1e5 + 111;		
const int LOG = 16;
		
int n, m;
int a, b;
vector <pair<int, int>> v[nax];

int h[nax];
int ans[nax];
pair<int, int> ed[nax];

int id;
int nr[nax];
bool odw[nax];
int low[nax];
stack <int> stos;

void dfs(int u, int ind) {
	stos.push(u);
	low[u] = h[u];
	odw[u] = 1;
	for(auto it : v[u]) {
		if(it.fi == ind)
			continue;
		if(!odw[it.se]) {
			h[it.se] = h[u] + 1;
			dfs(it.se, it.fi);
			low[u] = min(low[u], low[it.se]);
		}
		else {
			low[u] = min(low[u], h[it.se]);
		}
	}
	if(low[u] == h[u]) {
		id += 1;
		while(!stos.empty() && stos.top() != u) {
			nr[stos.top()] = id;
			stos.pop();
		}
		nr[u] = id;
		stos.pop();
	}		
}

vector <pair<int, int>> graf[nax];
pair<int, int> kraw[nax];
int q;

int sum[nax];
		
void solve(int u, int p = 0, int ind = -1) {
	odw[u] = 1;
	for(auto it : graf[u])
		if(!odw[it.se]) {
			solve(it.se, u, it.fi);
			sum[u] += sum[it.se];
		}
	if(ind != -1 && sum[u] != 0) {
		if(sum[u] > 0)
			kraw[ind] = mp(u, p);
		else
			kraw[ind] = mp(p, u);
	}
}
	

int main() {
	scanf("%d%d", &n, &m);
	FOR(i, 1, m) {
		scanf("%d%d", &a, &b);
		ed[i] = mp(a, b);
		if(a == b) {
			continue;
		}
		v[a].pb(mp(i, b));
		v[b].pb(mp(i, a));
	}
	
	FOR(i, 1, n) 
		if(!odw[i]) 
			dfs(i, -1);
	
	FOR(i, 1, n)
		for(auto it : v[i]) 
			if(nr[i] != nr[it.se]) 
				graf[i].pb(it);
	scanf("%d", &q);
	while(q--) {
		scanf("%d%d", &a, &b);
		if(nr[a] == nr[b])
			continue;
		sum[a] += 1;
		sum[b] -= 1;
	}
	
	FOR(i, 1, n)
		odw[i] = 0;
	FOR(i, 1, n)
		if(!odw[i])
			solve(i);
			
	FOR(i, 1, m) {
		if(kraw[i] == mp(0, 0))
			printf("B");
		else if(kraw[i] == ed[i])
			printf("R");
		else
			printf("L");
	}
		
	
		
		
	
	
	return 0;
}

Compilation message (stderr)

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]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
oneway.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40