oj.uz

Submission #94562

# Submission time Handle Problem Language Result Execution time Memory
94562 2019-01-20T17:58:26 Z jasony123123 One-Way Streets (CEOI17_oneway) C++11
100 / 100
 210 ms 29292 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7160 KB Output is correct
2 Correct 7 ms 7160 KB Output is correct
3 Correct 8 ms 7160 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 8 ms 7288 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 8 ms 7416 KB Output is correct
9 Correct 8 ms 7260 KB Output is correct
10 Correct 8 ms 7288 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7160 KB Output is correct
2 Correct 7 ms 7160 KB Output is correct
3 Correct 8 ms 7160 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 8 ms 7288 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 8 ms 7416 KB Output is correct
9 Correct 8 ms 7260 KB Output is correct
10 Correct 8 ms 7288 KB Output is correct
11 Correct 47 ms 12792 KB Output is correct
12 Correct 46 ms 13304 KB Output is correct
13 Correct 52 ms 14248 KB Output is correct
14 Correct 60 ms 16760 KB Output is correct
15 Correct 92 ms 17908 KB Output is correct
16 Correct 122 ms 23928 KB Output is correct
17 Correct 133 ms 24440 KB Output is correct
18 Correct 117 ms 23928 KB Output is correct
19 Correct 89 ms 25208 KB Output is correct
20 Correct 44 ms 12920 KB Output is correct
21 Correct 62 ms 12792 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7160 KB Output is correct
2 Correct 7 ms 7160 KB Output is correct
3 Correct 8 ms 7160 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 8 ms 7288 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 8 ms 7416 KB Output is correct
9 Correct 8 ms 7260 KB Output is correct
10 Correct 8 ms 7288 KB Output is correct
11 Correct 47 ms 12792 KB Output is correct
12 Correct 46 ms 13304 KB Output is correct
13 Correct 52 ms 14248 KB Output is correct
14 Correct 60 ms 16760 KB Output is correct
15 Correct 92 ms 17908 KB Output is correct
16 Correct 122 ms 23928 KB Output is correct
17 Correct 133 ms 24440 KB Output is correct
18 Correct 117 ms 23928 KB Output is correct
19 Correct 89 ms 25208 KB Output is correct
20 Correct 44 ms 12920 KB Output is correct
21 Correct 62 ms 12792 KB Output is correct
22 Correct 209 ms 27752 KB Output is correct
23 Correct 210 ms 26736 KB Output is correct
24 Correct 138 ms 26908 KB Output is correct
25 Correct 187 ms 29292 KB Output is correct
26 Correct 174 ms 27472 KB Output is correct
27 Correct 197 ms 26860 KB Output is correct
28 Correct 49 ms 13416 KB Output is correct
29 Correct 85 ms 15596 KB Output is correct
30 Correct 88 ms 15724 KB Output is correct
31 Correct 89 ms 15848 KB Output is correct
32 Correct 132 ms 19952 KB Output is correct