Submission #77682

#	Time	Username	Problem	Language	Result	Execution time	Memory
77682		updown1	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	16 ms	14712 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(ll i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define w cout
#define e endl
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define anc ancestor
const int MAXN = 100000;
//500,000,000 operations
int N, M, P, counter, dp[MAXN], num[MAXN], low[MAXN], parent[MAXN], N2;
int comp[MAXN], edges[MAXN][2], par[MAXN], anc[MAXN][20], q[MAXN][2], dep[MAXN];
bool visited[MAXN], up[MAXN], down[MAXN];
multiset <int> adj[MAXN];
vector <int> adj2[MAXN];
set<pair<int, int> > out;                ///BRIDGES IN OUT

void dfs(int x) {
	if (visited[x]) return;
	visited[x] = true;
	//w<< x s parent<<e;
	num[x] = low[x] = (++counter);
	int children = 0;
	for (int y : adj[x]) {
		if (!visited[y]) {
			children++;
			parent[y] = x;
			dfs(y);
			low[x] = min(low[x], low[y]);
			if (low[y] > num[x] && adj[x].count(y) < 2) out.insert(mp(min(x, y), max(x, y)) );
		}
		else if (parent[x] != y) {
			low[x] = min(low[x], num[y]);
		}
	}
}
void go(int at) {
    if (visited[at]) return;
    comp[at] = N2;
    visited[at] = true;
    for (int i: adj[at]) if (out.find(mp(min(at, i), max(at, i))) == out.end() ) {
        //w<< at+1 s "to" s i+1<<e;
        go(i);
    }
}
int LCA(int A, int B) {
	if (dep[A] > dep[B]) swap(A, B);
	int d = dep[B] - dep[A];
	For (i, 0, 18) {
		if (d&(1<<i) ) B = ancestor[B][i];
	}
	if (A == B) return A;

	for (int i=17; i>= 0; i--) {
		if (ancestor[A][i] != ancestor[B][i]) {
			A = ancestor[A][i];
			B = ancestor[B][i];
		}
	}
	return anc[A][0];
}
void go2(int at, int up) {
    par[at] = anc[at][0] = up;
    dep[at] = 1+dep[up];
    for (int i: adj2[at]) if (i != up) go2(i, at);
}
void adjust(int at) {
    for (int i: adj2[at]) if (i != par[at]) adjust(i), dp[at] += dp[i];
}


int main() {
	//ifstream cin ("test.in");
	ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    ffi low[i] = 10000000;

    ffj {
        int a, b; cin >> a >> b; a--; b--;
        edges[j][0] = a, edges[j][1] = b;
        adj[a].insert(b);
        adj[b].insert(a);
    }
    ffi dfs(i);

    ///BRIDGES IN OUT
    //w<< out.size()<<e; for (auto i: out) w<< (i).a+1 s (i).b+1<<e;
    ffi visited[i] = false;
    ffi if (!visited[i]) {
        go(i);
        N2++;
    }
    //ffi w<< i+1 s ":" s comp[i]+1<<e;
    ffi for (int j: adj[i]) if (comp[i] != comp[j]) adj2[comp[i]].pb(comp[j]);
    //For (i, 0, N2) {for (auto j: adj2[i]) w<< j+1 s " "; w<<e;}
    N = N2;
    dep[0] = -1, go2(0, 0);
    For (k, 0, 19) ffi anc[i][k+1] = anc[anc[i][k]][k];

    cin >> P;
    For (p, 0, P) {
        int a, b; cin >> a >> b; a--; b--; a = comp[a], b = comp[b];
        q[p][0] = a, q[p][1] = b;
        if (a == b) continue;
        int c = LCA(a, b);
        dp[a] += 1;
        dp[c] -= 1;
    }
    adjust(0);
    ffi {
        assert(dp[i] >= 0);
        if (dp[i] != 0) up[i] = true, dp[i] = 0;
    }
    For (p, 0, P) {
        int a = q[p][0], b = p[q][1];
        if (a == b) continue;
        int c = LCA(a, b);
        dp[b] += 1;
        dp[c] -= 1;
    }
    adjust(0);
    ffi if (dp[i] != 0) down[i] = true;
    //ffi w<< up[i] s down[i]<<e;
    ffj {
        int a = comp[edges[j][0]], b = comp[edges[j][1]];
        if (a == b) {w<< 'B'; continue;}
        //w<< a s b<<e;
        if (b == par[a]) {
            if (up[a]) w<< 'R';
            else if (down[a]) w<< 'L';
            else w<< 'B';
        }
        else {
            if (up[b]) w<< 'L';
            else if (down[b]) w<< 'R';
            else w<< 'B';
        }
    }
    w<<e;
}

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