oj.uz

답안 #825010

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
825010 2023-08-14T13:19:04 Z jamezzz One-Way Streets (CEOI17_oneway) C++17
100 / 100
 289 ms 32920 KB 
#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

9 11
9 1
1 2
2 9
1 3
3 4
4 5
5 6
6 4
2 7
7 8
7 8
3
7 3
1 3
4 3
*/

Compilation message

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

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 13268 KB Output is correct
2 Correct 6 ms 13268 KB Output is correct
3 Correct 7 ms 13268 KB Output is correct
4 Correct 8 ms 13340 KB Output is correct
5 Correct 7 ms 13396 KB Output is correct
6 Correct 7 ms 13272 KB Output is correct
7 Correct 8 ms 13340 KB Output is correct
8 Correct 8 ms 13396 KB Output is correct
9 Correct 6 ms 13340 KB Output is correct
10 Correct 7 ms 13236 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 13268 KB Output is correct
2 Correct 6 ms 13268 KB Output is correct
3 Correct 7 ms 13268 KB Output is correct
4 Correct 8 ms 13340 KB Output is correct
5 Correct 7 ms 13396 KB Output is correct
6 Correct 7 ms 13272 KB Output is correct
7 Correct 8 ms 13340 KB Output is correct
8 Correct 8 ms 13396 KB Output is correct
9 Correct 6 ms 13340 KB Output is correct
10 Correct 7 ms 13236 KB Output is correct
11 Correct 41 ms 19572 KB Output is correct
12 Correct 50 ms 20880 KB Output is correct
13 Correct 54 ms 22316 KB Output is correct
14 Correct 60 ms 24112 KB Output is correct
15 Correct 106 ms 24652 KB Output is correct
16 Correct 155 ms 26768 KB Output is correct
17 Correct 131 ms 28100 KB Output is correct
18 Correct 128 ms 26772 KB Output is correct
19 Correct 113 ms 29128 KB Output is correct
20 Correct 46 ms 20360 KB Output is correct
21 Correct 48 ms 20532 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 13268 KB Output is correct
2 Correct 6 ms 13268 KB Output is correct
3 Correct 7 ms 13268 KB Output is correct
4 Correct 8 ms 13340 KB Output is correct
5 Correct 7 ms 13396 KB Output is correct
6 Correct 7 ms 13272 KB Output is correct
7 Correct 8 ms 13340 KB Output is correct
8 Correct 8 ms 13396 KB Output is correct
9 Correct 6 ms 13340 KB Output is correct
10 Correct 7 ms 13236 KB Output is correct
11 Correct 41 ms 19572 KB Output is correct
12 Correct 50 ms 20880 KB Output is correct
13 Correct 54 ms 22316 KB Output is correct
14 Correct 60 ms 24112 KB Output is correct
15 Correct 106 ms 24652 KB Output is correct
16 Correct 155 ms 26768 KB Output is correct
17 Correct 131 ms 28100 KB Output is correct
18 Correct 128 ms 26772 KB Output is correct
19 Correct 113 ms 29128 KB Output is correct
20 Correct 46 ms 20360 KB Output is correct
21 Correct 48 ms 20532 KB Output is correct
22 Correct 289 ms 29956 KB Output is correct
23 Correct 188 ms 28496 KB Output is correct
24 Correct 152 ms 28692 KB Output is correct
25 Correct 200 ms 32920 KB Output is correct
26 Correct 227 ms 29616 KB Output is correct
27 Correct 182 ms 28516 KB Output is correct
28 Correct 56 ms 18244 KB Output is correct
29 Correct 63 ms 21864 KB Output is correct
30 Correct 62 ms 22196 KB Output is correct
31 Correct 65 ms 22276 KB Output is correct
32 Correct 121 ms 26064 KB Output is correct