Submission #1176538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176538		Dan4Life	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	114 ms	23656 KiB

oneway

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

#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

using ar2 = array<int,2>;
using ar3 = array<int,3>;

const int mxN = (int)1e5+10;
const int mxLg = 18;

map<ar2,int> cnt;
vector<ar3> edges;
int jmp[mxLg][mxN];
bitset<mxN> bridge;
int n, m, k, dfs_tim;
vector<ar2> adj[mxN];
int st[mxN], en[mxN], low[mxN], head[mxN], sub[mxN], ans[mxN];

template<int SZ>
struct DSU{
	int p[SZ], sz[SZ];
	void init(int n = SZ-1){
		for(int i = 1; i <= n; i++) p[i]=i,sz[i]=1; 
	}
	int findSet(int i){ return i==p[i]?i:p[i]=findSet(p[i]); }
	bool isSameSet(int i, int j){ return findSet(i)==findSet(j); }
	void unionSet(int i, int j){
		int x = findSet(i), y = findSet(j);
		if(x==y) return;
		if(sz[x]<sz[y])swap(x,y);
		p[y] = x, sz[x]+=sz[y];
	}
};
DSU<mxN> dsu;

template<int SZ>
struct Fenwick{
	int fen[SZ];
	void init(){
		for(int i = 0; i < SZ; i++) fen[i]=0;
	}
	void upd(int x, int v){
		for(++x;x<SZ;x+=x&-x) fen[x]+=v;
	}
	
	void upd(int x, int y, int v){
		if(x>y) return;
		upd(x,v); upd(y+1,-v);
	}
	
	int query(int x){
		int s = 0;
		for(++x; x>0; x-=x&-x)s+=fen[x];
		return s;
	}
};
Fenwick<mxN> fen;

void ae(int a, int b, int c){
	adj[a].pb({b,c}), adj[b].pb({a,c});
}

void dfsBridges(int s, int p){
	st[s] = low[s] = ++dfs_tim;
	bool ok = 0;
	for(auto [u,i] : adj[s]){
		if(u==p and !ok) {ok=1; continue;}
		if(!st[u]){
			dfsBridges(u,s);
			low[s] = min(low[s],low[u]);
			if(low[u]>st[s]) bridge[i] = 1;
		}
		else low[s] = min(low[s],st[u]);
	}
}

bool isAnc(int a, int b){
	return st[a]<=st[b] and en[a]>=en[b];
}

int lca(int a, int b){
	if(isAnc(a,b)) return a;
	if(isAnc(b,a)) return b;
	for(int i = mxLg-1; i>=0; i--)
		if(jmp[i][a] and !isAnc(jmp[i][a],b))
			a = jmp[i][a];
	return jmp[0][a];
}

void dfs(int s, int p){
	sub[s] = 1;
	for(int i = 0; i < sz(adj[s]); i++){
		auto [u,_] = adj[s][i];
		if(u==p) continue;
		dfs(u,s); sub[s]+=sub[u];
		if(adj[s][0][0]==p or sub[u] > sub[adj[s][0][0]])
			swap(adj[s][0], adj[s][i]); 
	}
}

void dfsHld(int s, int p, int h){
	st[s] = ++dfs_tim; 
	head[s] = h; jmp[0][s] = p;
	for(auto [u,_] : adj[s]){
		if(u==p) continue;
		dfsHld(u,s,u==adj[s][0][0]?h:u);
	}
	en[s] = dfs_tim;
}

void upd(int b, int a, int c){
	while(head[a]!=head[b]){
		fen.upd(st[head[b]],st[b],c);
		b = jmp[0][head[b]];
	}
	fen.upd(st[a]+1,st[b],c);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m; dsu.init(n);
	for(int i = 0; i < m; i++){
		int a, b; cin >> a >> b; ans[i] = 2;
		if(a!=b) edges.pb({a,b,i}), ae(a,b,i);
	}
	for(int i = 1; i <= n; i++)
		if(!st[i]) dfsBridges(i,0);
	
	for(auto [a,b,i] : edges)
		if(!bridge[i]) dsu.unionSet(a,b);
	for(int i = 1; i <= n; i++) adj[i].clear();
	for(auto [a,b,i] : edges)
		if(bridge[i]) ae(dsu.findSet(a),dsu.findSet(b),i);
		
	fill(st,st+n+1,0); fill(en,en+n+1,0); dfs_tim = 0;
	for(int i = 1; i <= n; i++){
		int s = dsu.findSet(i);
		if(s!=i or st[s]) continue;
		dfs(s,0); dfsHld(s,0,s);
	}
	for(int j = 1; j < mxLg; j++)
		for(int i = 1; i <= n; i++)
			jmp[j][i] = jmp[j-1][jmp[j-1][i]];
	cin >> k; fen.init();
	while(k--){
		int a, b, c; cin >> a >> b; 
		a = dsu.findSet(a), b=dsu.findSet(b);
		if(a==b) continue;
		c = lca(a,b);
		if(c==a) upd(b,c,-1);
		else if(c==b) upd(a,c,1);
		else upd(a,c,1), upd(b,c,-1);
	}
	for(auto [a,b,i] : edges){
		if(!bridge[i]) continue;
		a = dsu.findSet(a);
		b = dsu.findSet(b);
		bool ok = 0;
		if(st[a]>st[b])swap(a,b),ok=1;
		int v = fen.query(st[b]);
		if(v) ans[i]=(v<0)^ok;
	}
	for(int i = 0; i < m; i++) 
		cout << "LRB"[ans[i]]; cout << "\n";
}

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