Submission #94562

#	Time	Username	Problem	Language	Result	Execution time	Memory
94562		jasony123123	One-Way Streets (CEOI17_oneway)	C++11	100 / 100	210 ms	29292 KiB

oneway

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <array>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e12;
/***************************CEOI 17 Day 1 P1*************************************/

template<int NSZ, int ESZ> struct BCC {
	int NN, MM; // Nodes, Edges

	void init(int n, int m) {
		NN = n, MM = m;
	}

	v<pii> adj[NSZ];
	int edge[ESZ][2];

	void addEdge(int a, int b, int id) {
		edge[id][0] = a, edge[id][1] = b;
		adj[a].push_back({ b,id }), adj[b].push_back({ a,id });
	}

	bool bridge[ESZ];
	int lo[NSZ], ind[NSZ], t = 0;

	void tarjan(int cur, int par = -1) {
		ind[cur] = lo[cur] = t++;
		for (pii yi : adj[cur]) {
			int nex = yi.first, id = yi.second;
			if (id == par) continue;
			if (ind[nex] == -1) {
				tarjan(nex, id);
				lo[cur] = min(lo[cur], lo[nex]);
				if (lo[nex]>ind[cur]) bridge[id] = 1;
			}
			else lo[cur] = min(lo[cur], ind[nex]);
		}
	}

	void findBridges() {
		memset(ind, -1, sizeof ind);
		memset(lo, 0, sizeof lo);
		memset(bridge, 0, sizeof bridge);
		FOR(i, 0, NN) if (ind[i] == -1)
			tarjan(i);
	}

	bool vis[NSZ];
	int comp[NSZ], NC = 0;
	v<pii> adjc[NSZ]; // [from] = {to, id}

	void components(int cur, int c) {
		vis[cur] = 1, comp[cur] = c;
		for (pii yi : adj[cur]) {
			int nex = yi.first, id = yi.second;
			if (!vis[nex] && !bridge[id]) components(nex, c);
		}
	}

	void findComp() {
		memset(comp, -1, sizeof comp);
		memset(vis, 0, sizeof vis);
		FOR(i, 0, NN) if (!vis[i])
			components(i, NC++);
		FOR(i, 0, MM) if (bridge[i]) {
			int ca = comp[edge[i][0]], cb = comp[edge[i][1]];
			assert(ca!=cb);
			adjc[ca].push_back({ cb,i }), adjc[cb].push_back({ ca,i });
		}
	}
};

BCC<100000, 100000> bcc;
int N, M, depth[100000];
string ans;
pii par[100000]; // {node, edge id}

namespace LCA {
	const int MAXN = 100000, LOG = 16;

	int anc[MAXN][LOG];

	void setup(int N) {
		for (int j = 1; j < LOG; j++)
			for (int i = 0; i < N; i++)
				anc[i][j] = anc[anc[i][j - 1]][j - 1];
	}

	int lca(int x, int y) {
		if (depth[x] < depth[y])
			swap(x, y);
		int diff = depth[x] - depth[y];
		for (int i = LOG - 1; i >= 0; i--)
			if (diff >> i & 1)
				x = anc[x][i];
		if (x == y)
			return x;
		for (int i = LOG - 1; i >= 0; i--)
			if (anc[x][i] != anc[y][i]) {
				x = anc[x][i];
				y = anc[y][i];
			}
		return anc[x][0];
	}
}

void dfsDepths(int x, int p, int d) {
	LCA::anc[x][0] = p, depth[x] = d;
	for (pii c : bcc.adjc[x]) if (c.first != p) {
		par[c.first] = mp(x, c.second);
		dfsDepths(c.first, x, d + 1);
	}
}

int direction[100000];
void direct(int x, int g, int d) {
	if (x == g) return;
	if (direction[x] != 0)
		assert(direction[x] == d);
	else {
		direction[x] = d;
		
		pii myed;
		if (d == -1) // x, pars
			myed = { x, par[x].first };
		else  // par, x
			myed = { par[x].first, x };

		pii orded = mp(bcc.comp[bcc.edge[par[x].second][0]], bcc.comp[bcc.edge[par[x].second][1]]);

		if (myed == orded)
			ans[par[x].second] = 'R';
		else if (myed == mp(orded.second, orded.first))
			ans[par[x].second] = 'L';
		else
			assert(0);

		direct(par[x].first, g, d);
	}
}

int main() {
	io();
	cin >> N >> M;
	bcc.init(N, M);
	FOR(i, 0, M) {
		int a, b; cin >> a >> b;
		bcc.addEdge(a - 1, b - 1, i);
	}
	bcc.findBridges();
	ans.resize(M, 'B');
	bcc.findComp();

	memset(depth, -1, sizeof depth);
	FOR(i, 0, bcc.NC) if (depth[i] == -1)
		dfsDepths(i, -1, 0);
	LCA::setup(bcc.NC);

	memset(direction, 0, sizeof direction);
	int p; cin >> p;
	v < array<int, 4>> que;
	FOR(i, 0, p) {
		int a, b; cin >> a >> b;
		a = bcc.comp[a - 1], b = bcc.comp[b - 1];
		int c = LCA::lca(a, b);
		que.push_back({ depth[c], a, b, c });
	}
	sort(all(que));
	for (auto &q : que) {
		int a = q[1], b = q[2], c = q[3];
		direct(a, c, -1), direct(b, c, 1);
	}
	cout << ans << "\n";
}

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