Submission #868392

#	Time	Username	Problem	Language	Result	Execution time	Memory
868392		lovrot	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	2 ms	7512 KiB

oneway

#include <cstdio> 
#include <vector> 
#include <cstring> 

#define X first
#define Y second
#define MP make_pair
#define EB emplace_back

using namespace std;

typedef pair<int, int> pii;

const int N = 1e5 + 10;

int n, m, q, A[N], B[N];

int U[N];

int _find(int u) {
	if(U[u] == -1) return u;
	return U[u] = _find(U[u]);
}

void _union(int u, int v) {
	U[_find(u)] = _find(v);
}

int PE[N], DEP[N];
vector<pii> G[N];

int dfs(int u, int p) {	
	int sum = 0;
	for(pii e : G[u]) {	
		int v = e.X, ind = e.Y;
		if(ind == PE[u]) continue;
		else if(DEP[v] == -1) {
			DEP[v] = DEP[u] + 1;
			PE[v] = ind;
			sum += dfs(v, u);
		} else if(DEP[v] < DEP[u]) {
			++sum;
		} else if(DEP[v] > DEP[u]) { --sum; }
	}
	if(sum) _union(u, p);
	return sum;
}

int ANS[N], Q[N];
vector<pii> T[N];

void recon(int u, int p) {
	for(pii e : T[u]) {	
		int v = e.X, ind = e.Y;
		if(v != p) {
			PE[v] = ind;
			DEP[v] = DEP[u] + 1;
			recon(v, u);
		}
	}
}

int solve(int u, int p) {	
	int sum = Q[u];
	for(pii e : T[u]) {
		int v = e.X;
		if(v != p) sum += solve(v, u);
	}
	if(sum < 0) ANS[PE[u]] = u == B[PE[u]];
	else if(sum > 0) ANS[PE[u]] = p == B[PE[u]];
	return sum;
}

int main() {
	memset(U, -1, sizeof(U));
	memset(DEP, -1, sizeof(DEP)); 
	memset(ANS, -1, sizeof(ANS));

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		A[i] = u;
		B[i] = v;
		G[u].EB(MP(v, i));
		G[v].EB(MP(u, i));
	}
	
	DEP[1] = 0;
	dfs(1, 0);

	for(int i = 1; i <= m; ++i) {
		A[i] = _find(A[i]);
		B[i] = _find(B[i]);
		if(A[i] != B[i]) {
			T[A[i]].EB(MP(B[i], i));
			T[B[i]].EB(MP(A[i], i));
		}
	}

	DEP[1] = 0;
	recon(1, 0);

	scanf("%d", &q);

	for(int i = 0; i < q; ++i) {
		int u, v;
		scanf("%d%d", &u, &v); 
		u = _find(u);
		v = _find(v); 
		++Q[u];
		--Q[v];
	}

	solve(1, 0);

	for(int i = 1; i <= m; ++i) printf("%c", ANS[i] == -1 ? 'B' : (ANS[i] ? 'R' : 'L'));
	printf("\n");
	return 0;
}

Compilation message (stderr)

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

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