Submission #118520

#	Time	Username	Problem	Language	Result	Execution time	Memory
118520		zubec	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	572 ms	25424 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 100100;

vector <pair<int, int > > g[N];

int tin[N], fup[N], tim, tout[N], n, m;

int up[20][N];

bool used[N], isBridge[N];

void dfs(int v, int p){
    used[v] = 1;
    tin[v] = fup[v] = ++tim;
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i].first, id = g[v][i].second;
        if (id == p)
            continue;
        if (!used[to]){
            dfs(to, id);
            fup[v] = min(fup[v], fup[to]);
            if (tin[v] < fup[to]){
                isBridge[id] = 1;
            }
        } else {
            fup[v] = min(fup[v], tin[to]);
        }
    }
}

int clr[N], cnt;

void dfs2(int v, int p){
    clr[v] = cnt;
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i].first, id = g[v][i].second;
        if (isBridge[id] || clr[to] != 0)
            continue;
        dfs2(to, v);
    }
}

void dfs3(int v, int p){
    tin[v] = ++tim;
    up[0][v] = p;
    for (int i = 1; i < 20; i++){
        up[i][v] = up[i-1][up[i-1][v]];
    }
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i].first;
        if (to == p)
            continue;
        dfs3(to, v);
    }
    tout[v] = tim;
}

bool ifpred(int a, int b){
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int getlca(int a, int b){
    if (ifpred(a, b))
        return a;
    if (ifpred(b, a))
        return b;
    for (int i = 19; i >= 0; i--){
        int x = up[i][a];
        if (x != 0 && !ifpred(x, b))
            a = x;
    }
    return up[0][a];
}

vector <pair<pair<int, int>, int> > rebr;

int napr[2][N];
int anss[N];

void dfs4(int v, int p, int idpred){
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i].first, id = g[v][i].second;
        if (to == p)
            continue;
        dfs4(to, v, id);
        napr[0][v] += napr[0][to];
        napr[1][v] += napr[1][to];
    }
    if (napr[0][v] != 0){
        if (idpred > 0){
            anss[idpred] = 1;
        } else {
            anss[-idpred] = 2;
        }
    }
    if (napr[1][v] != 0){
        if (idpred > 0){
            anss[idpred] = 2;
        } else {
            anss[-idpred] = 1;
        }
    }
}

bool dfs5(int v, int need, int p){
    if (v == need)
        return 1;
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i].first, id = g[v][i].second;
        if (to == p)
            continue;
        if (dfs5(to, need, v)){
            if (id > 0){
                anss[id] = 2;
            } else {
                anss[-id] = 1;
            }
            return 1;
        }
    }
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        rebr.push_back({{u, v}, i});
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    for (int i = 1; i <= n; i++){
        if (!used[i])
            dfs(i, 0);
    }
    for (int i = 1; i <= n; i++){
        if (clr[i] == 0){
            ++cnt;
            dfs2(i, 0);
        }
    }
    for (int i = 1; i <= n; i++){
        g[i].clear();
    }
    for (int i = 0; i < rebr.size(); i++){
        int u = rebr[i].first.first, v = rebr[i].first.second, id = rebr[i].second;
        if (clr[u] != clr[v]){
            g[clr[u]].push_back({clr[v], id});
            g[clr[v]].push_back({clr[u], -id});
        }
    }
    //n = cnt;
    tim = 0;
    dfs3(1, 0);

    int tt;
    cin >> tt;
    int ttt = tt;
    while(tt--){
        int a, b;
        cin >> a >> b;
        if (clr[a] != clr[b]){
            a = clr[a];
            b = clr[b];
            int lca = getlca(a, b);
            ++napr[0][a];
            ++napr[1][b];
            --napr[0][lca];
            --napr[1][lca];
            //cout << "kek " << a << ' ' << b << endl;
            if (ttt <= 100)
            dfs5(a, b, 0);
        }
    }
    if (ttt > 1000)
    dfs4(1, 0, 0);
    for (int i = 1; i <= m; i++){
        if (anss[i] == 0)
            cout << 'B'; else
        if (anss[i] == 1)
            cout << 'L'; else
            cout << 'R';
    }

}

/**

5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3

*/

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs3(int, int)':
oneway.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs4(int, int, int)':
oneway.cpp:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'bool dfs5(int, int, int)':
oneway.cpp:112:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:152:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < rebr.size(); i++){
                     ~~^~~~~~~~~~~~~

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