제출 #303083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
303083		ly20	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	7 ms	10912 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345, MAXK = 20;
char resp[MAXN];
int low[MAXN];
vector <int> grafo[MAXN], id[MAXN];
pair <int, int> ar[MAXN];
int marc[MAXN], prof[MAXN], marc3[MAXN];
int t;
void dfs(int v, int p) {
	t++;
	prof[v] = t;
	low[v] = prof[v];
	marc[v] = 1;
	int idp = 0;
	for(int i = 0; i < grafo[v].size(); i++) {
		int viz = grafo[v][i];
		int id1 = id[v][i];
		if(id1 == p) {
			//idp = id[v][i];
			continue;
		}
		if(marc[viz] == 0) {
			//prof[viz] = prof[v] + 1;
			dfs(viz, id1);
			low[v] = min(low[v], low[viz]);
			if(low[viz] > prof[v]) {
				marc3[id[v][i]] = 1;
				//printf("%d %d %d\n", id[v][i], v, viz);
			}
		}
		else {
			low[v] = min(low[v], prof[viz]);
		}
		/*else {
			printf("N %d %d %d %d\n", v, viz, low[viz], prof[v]);
		}*/
	}
	//printf("%d %d %d %d\n", v, low[v], prof[v], idp);
}
int pai[MAXN], tam[MAXN];
int find(int v) {
	//printf("%d\n", v);
	if(pai[v] == v) return v;
	return pai[v] = find(pai[v]);
}
void une(int a, int b) {
	a = find(a); b = find(b);
	if(a == b) return;
	if(tam[a] < tam[b]) {
		pai[a] = b;
		tam[b] += tam[a];
	}
	else {
		pai[b] = a;
		tam[a] += tam[b]; 
	}
}
vector <int> grafo2[MAXN], id2[MAXN];
int dp[MAXN][MAXK];
void dfs1(int v, int p) {
	//printf("%d\n", v);
	dp[v][0] = p;
	for(int i = 0; i < grafo2[v].size(); i++) {
		int viz = grafo2[v][i];
		if(viz == p) continue;
		prof[viz] = prof[v] + 1;
		dfs1(viz, v);
	}
}
int lca(int a, int b) {
	if(prof[a] > prof[b]) swap(a, b);
	int d = prof[b] - prof[a];
	for(int i = 0; i < MAXK; i++) {
		if(d & (1 << i)) {
			b = dp[b][i];
		}
	}
	if(a == b) return a;
	for(int i = MAXK - 1; i >= 0; i--) {
		if(dp[a][i] != dp[b][i]) {
			a = dp[a][i]; b = dp[b][i];
		}
	}
	return dp[b][0];
}
int dec1[MAXN], sub[MAXN];
void dfs2(int v, int p) {
	int idp = 0;
	for(int i = 0; i < grafo2[v].size(); i++) {
		int viz = grafo2[v][i];
		if(viz == p) {
			idp = id2[v][i];
			continue;
		}
		dfs2(viz, v);
		dec1[v] += dec1[viz]; sub[v] += sub[viz];
	}
	int s, c;
	if(dec1[v] > 0) {
		c = v; s = p;
		//printf("%d %d\n", c, s);
		int a = find(ar[idp].first), b = find(ar[idp].second);
		if(a == s) {
			resp[idp] = 'R';
		}
		else {
			resp[idp] = 'L';
		}
	}
	else if(sub[v] > 0){
		c = p; s = v;
		//printf("%d %d\n", c, s);
		int a = find(ar[idp].first), b = find(ar[idp].second);
		if(a == s) {
			resp[idp] = 'R';
		}
		else {
			resp[idp] = 'L';
		}
	}
	else {
		resp[idp] = 'B';
	}
}
int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		grafo[a].push_back(b); grafo[b].push_back(a);
		id[a].push_back(i + 1); id[b].push_back(i + 1);
		ar[i + 1] = make_pair(a, b);
	}
	/*for(int i = 1; i <= m; i++) if(ar[i].first < ar[i].first) swap(ar[i].first, ar[i].second);
	sort(ar + 1, ar + m + 1);
	for(int i = 1; i < m; i++) {
		if(ar[i].first == ar[i + 1].first && ar[i].second == ar[i + 1].second) {
			while(true) {

			}
		}
	}*/
	dfs(1, 1);
	for(int i = 1; i <= n; i++) {
		pai[i] = i; tam[i] = 1;
	}
	for(int i = 1; i <= m; i++) {
		if(marc3[i] == 0 || marc3[i] == 2) {
			//printf("%d\n", i);
			resp[i] = 'B';
			une(ar[i].first, ar[i].second);
		}
	}
	for(int i = 1; i <= m; i++) {
		if(marc3[i] == 1) {
			int a = find(ar[i].first), b = find(ar[i].second); 
			//printf("%d %d\n", ar[i].first, ar[i].second);
			grafo2[a].push_back(b); grafo2[b].push_back(a);
			id2[a].push_back(i); id2[b].push_back(i); 
			//printf("%d %d %d\n", i, a, b);
		}
	}
	//printf("oi\n");
	int ini = find(1);
	prof[ini] = 0;
	//printf("oi\n");
	dfs1(ini, ini);
	//printf("oi\n");
	for(int i = 1; i < MAXK; i++) {
		for(int j = 1; j <= n; j++) {
			dp[j][i] = dp[dp[j][i - 1]][i - 1];
		}
	}
	//printf("oi\n");
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		a = find(a); b = find(b);
		if(a == b) continue;
		int c = lca(a, b);
		sub[c]--; dec1[c]--;
		sub[a]++; dec1[b]++;
	}
	dfs2(ini, ini);
	for(int i = 1; i <= m; i++) {
		printf("%c", resp[i]);
	}
	printf("\n");
	return 0;
}

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

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i = 0; i < grafo[v].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~
oneway.cpp:15:6: warning: unused variable 'idp' [-Wunused-variable]
   15 |  int idp = 0;
      |      ^~~
oneway.cpp: In function 'void dfs1(int, int)':
oneway.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i = 0; i < grafo2[v].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:90:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for(int i = 0; i < grafo2[v].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~
oneway.cpp:103:32: warning: unused variable 'b' [-Wunused-variable]
  103 |   int a = find(ar[idp].first), b = find(ar[idp].second);
      |                                ^
oneway.cpp:114:32: warning: unused variable 'b' [-Wunused-variable]
  114 |   int a = find(ar[idp].first), b = find(ar[idp].second);
      |                                ^
oneway.cpp:99:9: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   99 |  int s, c;
      |         ^
oneway.cpp: In function 'int main()':
oneway.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  131 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:178:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  178 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
oneway.cpp:181:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  181 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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