제출 #394845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
394845		Noureldin	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	3 ms	3148 KiB

oneway

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define loop(i,n) for(int i = 0;i < (n);i++)
#define all(A) A.begin(),A.end()
#define pb push_back
#define mp make_pair
#define sz(A) ((int)A.size())
typedef std::vector<int> vi;
typedef std::pair<int,int> pi;
typedef std::vector<pi> vp;
typedef long long ll;
#define popcnt(x) __builtin_popcount(x)
#define LSOne(x) ((x) & (-(x)))
#define print(A,t) cerr << #A << ": "; copy(all(A),ostream_iterator<t>(cerr," " )); cerr << endl
#define prArr(A,n,t)  cerr << #A << ": "; copy(A,A + n,ostream_iterator<t>(cerr," " )); cerr << endl
#define PRESTDIO() cin.tie(0),cerr.tie(0),ios_base::sync_with_stdio(0)
#define what_is(x) cerr << #x << " is " << x << endl
#define bit_lg(x) (assert(x > 0),__builtin_ffsll(x) - 1)
const double PI = acos(-1);
template<class A,class B>
std::ostream& operator << (std::ostream& st,const std::pair<A,B> p) {
	st << "(" << p.first << ", " << p.second << ")";
	return st;
}
void tc();
auto test_cases = []() {
	int T; scanf("%d", &T);
	while(T--) tc();
};
using namespace std;

const int MAXN = 100*1000 + 10;
int dfs_num[MAXN], dfs_low[MAXN], dfs_time;
list<int> E[MAXN];
vi fr, to;
vector<bool> isBridge;
int n, m, p;

void dfs(int u, int ie){
	dfs_low[u] = dfs_num[u] = dfs_time++;
	for(int e : E[u]) if(e != ie) {
		int v = fr[e] + to[e] - u;
		if(dfs_num[v] == -1){
			dfs(v, e);
			if(dfs_low[v] > dfs_num[u]) {
				isBridge[e] = true;
			}
			dfs_low[u] = min(dfs_low[u], dfs_low[v]);
		} else {
			dfs_low[u] = min(dfs_low[u], dfs_num[v]);
		}
	}
}

int id[MAXN], W[MAXN];
int find(int a){
	return id[a] = (a == id[a]) ? a : find(id[a]);
}
void join(int a, int b){
	a = find(a);
	b = find(b);
	if(a == b) return;
	if(W[a] < W[b]) swap(a, b);
	W[a] += W[b];
	id[b] = a;
	E[a].splice(E[a].end(), E[b]);
}

const int MAXLG = 20;
int depth[MAXN], P[MAXN][MAXLG];
int dfs_in[MAXN], dfs_out[MAXN];

void dfs2(int u, int p) {
	dfs_in[u] = dfs_num[u] = dfs_time++;
	depth[u] = depth[p] + 1;
	P[u][0] = p;
	loop(k, MAXLG - 1) P[u][k + 1] = P[P[u][k]][k];
	for(int e : E[u]) {
		int v = find(fr[e]) + find(to[e]) - u;
		if(v == p) continue;
		dfs2(v, u);
	}
	dfs_out[u] = dfs_time - 1;
}

bool inSubTree(int a,int b){
	return dfs_in[b] <= dfs_in[a] && dfs_in[a] <= dfs_out[b];
}
 
int lca(int a,int b){
	if(depth[a] > depth[b]) swap(a,b);
	if(inSubTree(b,a)) return a;
	int k = MAXLG - 1;
	while(a != b){
		if(depth[a] > depth[b]) swap(a,b);		
		while(k && inSubTree(a,P[b][k])) k--;
		b = P[b][k];
	}
	return a;
}


int val[MAXN];
vi edgeVal;

int dfs3(int u, int p){
	int ret = val[u];
	dfs_num[u] = 1;
	for(int e : E[u]) {
		int v = find(fr[e]) + find(to[e]) - u;
		if(v == p) continue;
		int tmp = dfs3(v, u);
		edgeVal[e] = tmp;
		ret += tmp;
	}
	return ret;
}

int main(){
#ifdef HOME
	freopen("in.in", "r", stdin);
#endif
	scanf("%d %d", &n, &m);
	loop(e, m){
		int a, b; scanf("%d %d", &a, &b);
		fr.push_back(a);
		to.push_back(b);
		isBridge.push_back(false);
		E[a].push_back(e);
		E[b].push_back(e);
	}
	memset(dfs_num, -1, sizeof dfs_num);
	for(int i = 1; i <= n; i++) if(dfs_num[i] == -1) dfs(i, -1);
	fill(W, W + n + 1, 1);
	iota(id, id + n + 1, 0);
	loop(e, m) if(!isBridge[e]) join(fr[e], to[e]);
	vi V;
	for(int i = 1; i <= n; i++) if(i == find(i)) V.push_back(i);
	list<int> aux;
	for(int i : V){
		aux.clear();
		for(int e : E[i]) if(isBridge[e]){
			aux.push_back(e);
		}
		E[i].swap(aux);
	}
	memset(dfs_num, -1, sizeof dfs_num);
	dfs_time = 0;
	for(int i : V) if(dfs_num[i] == -1) dfs2(i, 0);
	dfs_out[0] = dfs_time;
	edgeVal.resize(m, 0);
	scanf("%d", &p);
	while(p--){
		int a, b; scanf("%d %d", &a, &b);
		a = find(a), b = find(b);
		if(a == b) continue;
		int p = lca(a, b);
		if(p == a) {
			val[a]++;
			val[b]--;
		} else if(p == b) {
			val[a]--;
			val[b]++;
		} else {
			val[a]++;
			val[b]--;
		}
	}
	memset(dfs_num, -1, sizeof dfs_num);
	for(int i : V) if(dfs_num[i] == -1) dfs3(i, 0);

	loop(e, m) {
		if(!isBridge[e] || edgeVal[e] == 0) putchar('B');
		else {
			int a0 = find(fr[e]), b0 = find(to[e]);
			int a = a0, b = b0;
			if(depth[a] > depth[b]) swap(a, b);
			if(edgeVal[e] > 0) swap(a, b);
			putchar("LR"[a == a0]);
		}
	}
	puts("");
	return 0;
}

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

oneway.cpp: In function 'int main()':
oneway.cpp:123:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:125:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |   int a, b; scanf("%d %d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:152:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  152 |  scanf("%d", &p);
      |  ~~~~~^~~~~~~~~~
oneway.cpp:154:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  154 |   int a, b; scanf("%d %d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~

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