제출 #824990

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

oneway

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define psf push_front
#define ppb pop_back
#define ppf pop_front
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar_unlocked();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 100005

int n,m,a[maxn],b[maxn],q,x[maxn],y[maxn];
int num[maxn],par[maxn],low[maxn],cnt,bridge[maxn];
int upar[maxn],bcnt,bcc[maxn];
int p[20][maxn],vis[maxn],dep[maxn];
ii to[maxn];
char ans[maxn];
stack<int> s;
vector<ii> AL[maxn],AL2[maxn];

void dfs(int u){
	num[u]=low[u]=cnt++;
	s.push(u);
	for(auto[v,i]:AL[u]){
		if(num[v]==-1){
			par[v]=u;
			dfs(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>num[u]){
				bridge[i]=true;
			}
		}
		else if(v!=par[u]){
			low[u]=min(low[u],num[v]);
		}
	}
}

int fp(int i){
	return upar[i]==i?i:upar[i]=fp(upar[i]);
}

void join(int x,int y){
	upar[fp(x)]=fp(y);
}

void dfs2(int u){
	vis[u]=true;
	for(int k=1;k<20;++k){
		if(p[k-1][u]!=-1){
			p[k][u]=p[k-1][p[k-1][u]];
		}
	}
	for(auto[v,i]:AL2[u]){
		if(p[0][u]==v)continue;
		p[0][v]=u;
		dep[v]=dep[u]+1;
		dfs2(v);
	}
}

int lca(int a,int b){
	if(dep[a]>dep[b])swap(a,b);
	for(int k=19;k>=0;--k){
		if(p[k][a]!=-1&&dep[p[k][a]]>=dep[b])a=p[k][a];
	}
	if(a==b)return a;
	for(int k=19;k>=0;--k){
		if(p[k][a]!=p[k][b])a=p[k][a],b=p[k][b];
	}
	return p[0][a];
}

//returns dep to, dir
ii dfs3(int u){
	ii res=to[u];
	for(auto[v,i]:AL2[u]){
		if(p[0][u]==v)continue;
		ii pr=dfs3(v);
		if(pr.fi<=dep[u]){
			if(pr.se==0){//up
				if(bcc[a[i]]==v)ans[i]='R';
				else ans[i]='L';
			}
			else{//down
				if(bcc[a[i]]==u)ans[i]='R';
				else ans[i]='L';
			}
		}
		else ans[i]='B';
		res=min(res,pr);
	}
	return res;
}

int main(){
	sf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		sf("%d%d",&a[i],&b[i]);
		AL[a[i]].pb({b[i],i});
		AL[b[i]].pb({a[i],i});
	}
	sf("%d",&q);
	for(int i=0;i<q;++i){
		sf("%d%d",&x[i],&y[i]);
	}
	memset(num,-1,sizeof num);
	for(int i=1;i<=n;++i){
		if(num[i]==-1){
			dfs(i);
			if(sz(AL[i])==1){
				bridge[AL[i][0].se]=true;
			}
		}
		upar[i]=i;
	}
	for(int i=0;i<m;++i){
		if(!bridge[i]){
			join(a[i],b[i]);
		}
	}
	for(int i=1;i<=n;++i){
		if(fp(i)==i)bcc[i]=bcnt++;
	}
	for(int i=1;i<=n;++i){
		bcc[i]=bcc[fp(i)];
	}
	for(int i=0;i<m;++i){
		if(bcc[a[i]]==bcc[b[i]]){
			ans[i]='B';
		}
		else{
			int u=bcc[a[i]],v=bcc[b[i]];
			AL2[u].pb({v,i});
			AL2[v].pb({u,i});
		}
	}
	memset(p,-1,sizeof p);
	for(int i=0;i<bcnt;++i){
		if(!vis[i])dfs2(i);
		to[i]={dep[i],2};
	}
	for(int i=0;i<q;++i){
		int u=bcc[x[i]],v=bcc[y[i]];
		int l=lca(u,v);
		if(u!=l){
			to[u]=min(to[u],{dep[l],0});//up
		}
		if(v!=l){
			to[v]=min(to[v],{dep[l],1});//down
		}
	}
	for(int i=0;i<bcnt;++i){
		if(p[0][i]==-1)dfs3(i);
	}
	for(int i=0;i<m;++i)pf("%c",ans[i]);
	pf("\n");
}

/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/

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

oneway.cpp: In function 'int main()':
oneway.cpp:149:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |  sf("%d%d",&n,&m);
      |    ^
oneway.cpp:151:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |   sf("%d%d",&a[i],&b[i]);
      |     ^
oneway.cpp:155:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |  sf("%d",&q);
      |    ^
oneway.cpp:157:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |   sf("%d%d",&x[i],&y[i]);
      |     ^

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