제출 #1133028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133028		RSAMSD	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	334 ms	46264 KiB

oneway

#include <bits/stdc++.h>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O2","O3","O1")
#pragma GCC optimize("Ofast")
using namespace std;
ifstream fin("input.txt");
ofstream fout("output.txt");
int t = 0;
int const f = 1e5 + 10;
long long mod = 998244353;
int a[f];
int b[f];
char p[f];
long long dp1[f];
long long dp2[f];
int tr[f];
int cnt =0;
pair<int,int>e[f];
int par[30][f];
pair<int,int> o[f];
int sb[f];
vector<int>g[f];
vector<int>g2[f];
vector<long long> vi;
vector<int>vv[f];
map<pair<int,int>,long long> conv;
// map<long long, long long> cnv;
struct node {
	int val;
	pair<int,int>frontmin,frontmax,backmin,backmax;
	node(){
		val =0;
		frontmax = frontmin=backmin=backmax ={-1,-1};
	}
};
bool B[f];
bool F[f];
// node segtree[f * 4];
// long long fen[f];
int dfs(int v){
	B[v] = 1;
	int run =0;
	a[v]-=dp2[v];
	b[v]-=dp2[v];
	for(int u:g[v]){
		if(B[u]){
			if(dp1[u]<dp1[v]){
				tr[u]++;
				run++;
			}
			continue;
		}
		run+=dfs(u);
		a[v]+=a[u];
		b[v]+=b[u];
	}
	run-=tr[v];
	if(v==1)return 0;
	if(run>1||(a[v]==0&&b[v]==0)){
		p[conv[{v,par[0][v]}]] = 'B';
		// cout<<(run>0)<<" : : "<<v<<'\n';
	}
	else if(a[v]>0&&b[v]>0){
		while(true){
			run++;
		}
	}
	else {
		// cout<<v<< par[0][v]<<'\n';
		if(a[v]>0){
			if(e[conv[{v,par[0][v]}]].first==v)p[conv[{v,par[0][v]}]] = 'R';
			else p[conv[{v,par[0][v]}]] = 'L';
		}
		else{
			if(e[conv[{v,par[0][v]}]].first==v)p[conv[{v,par[0][v]}]] = 'L';
			else p[conv[{v,par[0][v]}]] = 'R';
		}
	}
	return run;
}
void dfs2(int v,int parv){
	F[v] = 1;
	dp1[v] = dp1[parv]+1;
	par[0][v] = parv;
	for(int u:g[v]){
		if(!F[u]){
			B[conv[{v,u}]] = 1;
			dfs2(u,v);
		}
	}
}
long long lca(int v,int k){
	if(k==0)return v;
	int gg = log2(k);
	return lca(par[gg][v],k-(1<<gg));
}
long long powmod(long long a, long long p, long long modd) {
	long long ans = 1;
	while (p > 0) {
		if (p % 2 == 1) {
			ans *= a;
			ans %= modd;
			p--;
		}
		if (p == 0)break;
		a *= a;
		a %= modd;
		p /= 2;
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	t = 1;
	// cin >> t;
	for (int hhh = 1;hhh <= t;hhh++) {
		long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 1, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
		string s1;
		char s3;
		string s2;
		string tt;
		bool c = 1;
		long double pi = 3.14159265359;
		long double num =0;
		long double num2;
		priority_queue<pair<long long, long long>> qq;
		queue<int> qu;
		queue<pair<long long,pair<long long,long long>>> qm;
		pair<int,int> aa;
		map<long long,long long> convbeg;
		set<long long> vv;
		cin>>n>>m;
		for(int i =1;i<=m;i++){
			cin>>l>>r;
			e[i] = {l,r};
			conv[{l,r}] = conv[{r,l}] = i;
			g[l].push_back(r);
			g[r].push_back(l);
		}
		for(int i =1;i<=n;i++){
			if(!F[i])dfs2(i,0);
		}
		for(int i =1;i<=m;i++){
			if(!B[i])p[i] = 'B';
			else conv[e[i]] = conv[{e[i].second,e[i].first}] = i;
		}
		if(B[0]){
				while(true){
					k2++;
				}
		}
		fill(B,B+n+1,0);
		for(int j =1;j<30;j++){
			for(int i =1;i<=n;i++){
				par[j][i] = par[j-1][par[j-1][i]];
			}
		}
		cin>>d;
		for(int i =0;i<d;i++){
			cin>>l>>r;
			a[l]++;
			b[r]++;
			if(dp1[l]>dp1[r])swap(l,r);
			r = lca(r,dp1[r]-dp1[l]);
			// cout<<i<<" : "<<'\n';
			for(int j = log2(n);j>-1;j--){
				if(par[j][l]!=par[j][r]){
					l = par[j][l];
					r = par[j][r];
					// cout<<l<<r<<'\n';
				}
			}
			if(r!=l)r =par[0][r];
			dp2[r]++;
			// cout<<r<<l<<'\n';
		}
		for(int i =1;i<=n;i++)if(!B[i])dfs(i);
		for(int i =1;i<=m;i++){
			if(p[i]!='B'&&p[i]!='R'&&p[i]!='L'){
				while(true){
					k2++;
				}
			}
			cout<<p[i];
		}
	}
}

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