Submission #1115110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115110		Icelast	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	336 KiB

oneway

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct Tree{
    int n, root;
    vector<int> depth, head, sz, pa;
    vector<int> f;
    Tree(int n, int root, vector<vector<int>> &adj): n(n), root(root){
        depth.resize(n+1, -1);
        head.resize(n+1);
        sz.resize(n+1, 0);
        pa.resize(n+1, -1);
        auto rootTree = [&](auto rootTree, int u, int p) -> void{
            depth[u] = depth[p]+1;
            pa[u] = p;
            sz[u] = 1;
            for(int v : adj[u]){
                if(v == p) continue;
                rootTree(rootTree, v, u);
                sz[u] += sz[v];
            }
        };
        rootTree(rootTree, root, 0);
        auto decompose = [&](auto decompose, int u, int h) -> void{
            head[u] = h;
            int heavy = -1;
            for(int v : adj[u]){
                if(v == pa[u]) continue;
                if(heavy == -1 || sz[heavy] < sz[v]) heavy = v;
            }
            if(heavy != -1) decompose(decompose, heavy, h);
            for(int v : adj[u]){
                if(v == pa[u] || v == heavy) continue;
                decompose(decompose, v, v);
            }
        };
        decompose(decompose, root, root);
        f = [&]{
            vector<array<int, 2>> first(n+1);
            vector<array<int, 2>> second(n+1);
            function<void(int, int)> dfs0 = [&](int u, int p) {
                first[u] = second[u] = {0, -1};
                for (int v : adj[u]) {
                    if (v == p) {
                        continue;
                    }
                    dfs0(v, u);
                    auto fetch = first[v];
                    fetch[0] += 1;
                    fetch[1] = v;
                    if (fetch > first[u]) {
                        swap(fetch, first[u]);
                    }
                    if (fetch > second[u]) {
                        swap(fetch, second[u]);
                    }
                }
            };
            dfs0(1, 0);

            function<void(int, int)> dfs = [&](int u, int p) {
                for (int v : adj[u]) {
                    if (v == p) {
                        continue;
                    }
                    auto fetch = first[u][1] == v ? second[u] : first[u];
                    fetch[0] += 1;
                    fetch[1] = u;
                    if (fetch > first[v]) {
                        swap(fetch, first[v]);
                    }
                    if (fetch > second[v]) {
                        swap(fetch, second[v]);
                    }
                    dfs(v, u);
                }
            };
            dfs(1, 0);
            vector<int> f(n+1);
            for (int u = 1; u <= n; u++) {
                f[u] = first[u][0];
            }
            return f;
        }();
    };
    int lca(int u, int v){
        for(; head[u] != head[v]; v = pa[head[v]]){
            if(depth[head[u]] > depth[head[v]]) swap(u, v);
        }
        if(depth[u] > depth[v]) swap(u, v);
        return u;
    }
    int dist(int u, int v) {
        return depth[u]+depth[v]-2*depth[lca(u, v)];
    }
};
struct path{
    int u, v, lca;
};
struct edge{
    int v, id, val;
};
struct edg{
    int u, v;
};
void BridgeTree(int n, vector<vector<edge>> adj, vector<vector<edge>> &tree, vector<int> &comp, vector<int> &bridge){
    vector<int> tin(n+1), low(n+1), stk;
    vector<bool> vis(n+1, 0);
    fill(comp.begin(), comp.end(), -1);
    tree.emplace_back();
    int timer = 0, id = 0;
    auto dfs = [&](auto dfs, int u, int p) -> void{
        vis[u] = true;
        stk.push_back(u);
        timer++;
        low[u] = tin[u] = timer;
        bool skipped = false;
        for(auto it : adj[u]){
            int v = it.v, id = it.id;
            if(v == p && !skipped){
                skipped = true;
                continue;
            }
            if(vis[v]){
                low[u] = min(low[u], tin[v]);
            }else{
                dfs(dfs, v, u);
                low[u] = min(low[u], low[v]);
                if(low[v] > tin[u]){
                    bridge.push_back(id);
                }
            }
        }
        if(low[u] == tin[u]){
            int v;
            id++;
            tree.emplace_back();
            do{
                v = stk.back();
                stk.pop_back();
                comp[v] = id;
                for(auto it : adj[v]) {
                    int w = it.v, id = it.id;
                    if(comp[w] != -1 && comp[w] != comp[v]){
                        tree[comp[w]].push_back({comp[v], id});
                        tree[comp[v]].push_back({comp[w], id});
                    }
                }
            }while(v != u);
        }
    };
    dfs(dfs, 1, 0);
}
void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<edge>> adj(n+1);
    vector<edg> e(m+1);
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        e[i] = {u, v};
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    //bridge tree
    vector<vector<edge>> tree;
    vector<int> comp(n+1, -1), bridge;
    BridgeTree(n, adj, tree, comp, bridge);
    int N = tree.size()-1;
    vector<vector<int>> tree2(N+1);
    for(int i = 1; i < tree.size(); i++){
        for(auto it : tree[i]){
            int j = it.v;
            tree2[i].push_back(j);
        }
    }
    Tree Y(n, 1, tree2);
    int p;
    cin >> p;
    vector<path> pth(p+1);
    for(int i = 1; i <= p; i++){
        cin >> pth[i].u >> pth[i].v;
        pth[i].u = comp[pth[i].u];
        pth[i].v = comp[pth[i].v];
        pth[i].lca = Y.lca(pth[i].u, pth[i].v);
    }
    sort(pth.begin()+1, pth.end(), [&](path a, path b){return Y.depth[a.lca] < Y.depth[b.lca];});
    vector<edge> pa(N+1, {0, 0, 0});
    auto dfs = [&](auto dfs, int u, int p) -> void{
        for(auto it : tree[u]){
            int v = it.v, id = it.id;
            if(v == p) continue;
            pa[v] = {u, id, 0};
            dfs(dfs, v, u);
        }
    };
    dfs(dfs, 1, 0);

    vector<int> ud(m+1, 0);
    for(int i = 1; i <= p; i++){
        int u = pth[i].u, v = pth[i].v;
        while(u != pth[i].lca && pa[u].val == 0){
            ud[pa[u].id] = 1;
            pa[u].val = 1;
            u = pa[u].v;
        }
        while(v != pth[i].lca && pa[v].val == 0){
            ud[pa[v].id] = -1;
            pa[v].val = -1;
            v = pa[v].v;
        }
    }
    vector<char> ans(m+1, ' ');
    vector<bool> non_bridge(m+1, true);
    for(int i : bridge){
        non_bridge[i] = false;
    }
    for(int i = 1; i <= m; i++){
        if(non_bridge[i]){
            ans[i] = 'B';
        }else{
            if(ud[i] == -1){
                if(Y.depth[comp[e[i].u]] < Y.depth[comp[e[i].v]]){
                    ans[i] = 'R';
                }else{
                    ans[i] = 'L';
                }
            }else{
                if(Y.depth[comp[e[i].u]] < Y.depth[comp[e[i].v]]){
                    ans[i] = 'L';
                }else{
                    ans[i] = 'R';
                }
            }
        }
    }
    for(int i = 1; i <= m; i++){
        cout << ans[i];
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Compilation message (stderr)

oneway.cpp: In function 'void solve()':
oneway.cpp:174:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<edge> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |     for(int i = 1; i < tree.size(); i++){
      |                    ~~^~~~~~~~~~~~~

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