제출 #868396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
868396		lovrot	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	67 ms	21756 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) {
			DEP[v] = DEP[u] + 1;
			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));
	}
	
	memset(DEP, -1, sizeof(DEP));
	for(int i = 1; i <= n; ++i) 
		if(DEP[i] == -1) {
			DEP[i] = 0;
			dfs(i, 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));
		}
	}
	
	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];
	}

	memset(DEP, -1, sizeof(DEP));
	for(int i = 1; i <= n; ++i) 
		if(DEP[_find(i)] == -1) {
			DEP[_find(i)] = 0;
			solve(i, 0);
		}

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

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp: In function 'int main()':
oneway.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  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]
   86 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
oneway.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

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