Submission #249154

#	Time	Username	Problem	Language	Result	Execution time	Memory
249154		Sorting	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	7 ms	9856 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

const int k_N = 1e5 + 3;

struct DisjointSetUnion{
    int p[k_N], sz[k_N];

    DisjointSetUnion(){}

    void resize(int n){
        for(int i = 1; i <= n; ++i){
            p[i] = i;
            sz[i] = 1;
        }
    }

    int get_p(int x){
        if(p[x] == x) return x;
        return p[x] = get_p(p[x]);
    }

    bool unite(int u, int v){
        if(get_p(u) == get_p(v))
            return false;

        if(sz[p[u]] < sz[p[v]])
            swap(u, v);
        sz[p[u]] += sz[p[v]];
        p[p[v]] = p[u];

        return true;
    }
};

int n, m, p;
vector<pair<int, int>> adjacent[k_N];
pair<int, int> edges[k_N];

bool used[k_N];
int depth[k_N];
char ans[k_N];

DisjointSetUnion dsu;
vector<int> adj_dsu[k_N], adj2[k_N];
vector<pair<int, bool>> ve[k_N];

int lca[20][k_N], lca_par[k_N];

void dfs_lca(int node){
    for(int to: adj2[node]){
        if(to == lca_par[node])
            continue;

        lca_par[to] = node;
        depth[to] = depth[node] + 1;
        dfs_lca(to);
    }
}

void init_lca(){
    for(int i = 1; i <= n; ++i) used[i] = false;

    for(int i = 1; i <= n; ++i){
        int x = dsu.get_p(i);
        if(!used[x]){
            depth[x] = 0;
            lca_par[x] = dsu.get_p(x);
            dfs_lca(x);
        }
    }

    for(int j = 1; j <= n; ++j)
        lca[0][j] = lca_par[j];

    for(int i = 1; i < 20; ++i)
        for(int j = 1; j <= n; ++j)
            lca[i][j] = lca[i - 1][lca[i - 1][j]];
}

int get_lca(int u, int v){
    if(depth[u] < depth[v])
        swap(u, v);
    int diff = depth[u] - depth[v];
    for(int i = 19; i >= 0; --i)
        if(diff & (1 << i))
            u = lca[i][u];

    if(u == v) return u;

    for(int i = 19; i >= 0; --i){
        if(lca[i][u] != lca[i][v]){
            u = lca[i][u];
            v = lca[i][v];
        }
    }
    return lca[0][u];
}

int cycle(int node, int p_idx){
    used[node] = true;

    int ret = node;
    for(auto [to, idx]: adjacent[node]){
        if(idx == p_idx)
            continue;
        if(used[to]){
            ans[idx] = 'B';
            if(depth[to] < depth[ret]) ret = to;
        }
        else{
            depth[to] = depth[node] + 1;
            int x = cycle(to, idx);
            if(x != to) ans[idx] = 'B';
            if(depth[x] < depth[ret]) ret = x;
        }
    }

    return ret;
}

pair<int, bool> dfs(int node){
    //cout << "dfs " << node << "\n";
    used[node] = true;

    pair<int, bool> ret{node, false};
    for(int idx: adj_dsu[node]){
        int to;
        if(dsu.get_p(edges[idx].first) == node) to = dsu.get_p(edges[idx].second);
        else to = dsu.get_p(edges[idx].first);

        if(used[to])
            continue;

        depth[to] = depth[node] + 1;
        pair<int, bool> curr = dfs(to);
        if(depth[curr.first] <= depth[node]) ans[idx] = (curr.second ^ (dsu.get_p(edges[idx].first) == node)) ? 'R' : 'L';
        if(depth[curr.first] < depth[ret.first]) ret = curr;
    }

    for(auto p: ve[node]){
        if(depth[p.first] == -1) continue;
        //cout << node << " nodenonde " << p.first << " " << p.second << "\n";
        if(depth[p.first] < depth[ret.first]) ret = p;
    }

    //cout << "return " << node << " - " << ret.first << " " << ret.second << "\n";
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;

        adjacent[u].push_back({v, i});
        adjacent[v].push_back({u, i});
        ans[i] = 'U';
        edges[i] = {u, v};
    }

    for(int i = 1; i <= n; ++i){
        if(!used[i]){
            depth[i] = 0;
            cycle(i, -1);
        }
    }

    dsu.resize(n);
    for(int i = 0; i < m; ++i)
        if(ans[i] == 'B')
            dsu.unite(edges[i].first, edges[i].second);

    for(int i = 0; i < m; ++i){
        if(ans[i] == 'U'){
            int pf = dsu.get_p(edges[i].first), ps = dsu.get_p(edges[i].second);
            adj_dsu[pf].push_back(i);
            adj_dsu[ps].push_back(i);

            adj2[pf].push_back(ps);
            adj2[ps].push_back(pf);
        }
    }

    cin >> p;
    for(int i = 0; i < p; ++i){
        int u, v;
        cin >> u >> v;

        int pu = dsu.get_p(u), pv = dsu.get_p(v);
        if(pu != pv){
            int lca = get_lca(pu, pv);
            if(lca == pu || lca == pv){
                ve[pu].push_back({pv, true});
                ve[pv].push_back({pu, false});
            }
            else{
                ve[pu].push_back({lca, true});
                ve[pv].push_back({lca, false});
            }
        }
    }

    for(int i = 1; i <= n; ++i){
        used[i] = false;
        depth[i] = -1;
    }

    for(int i = 1; i <= n; ++i){
        int pi = dsu.get_p(i);
        if(!used[pi]){
            depth[pi] = 0;
            dfs(pi);
        }
    }
    
    for(int i = 0; i < m; ++i)
        if(ans[i] == 'U')
            ans[i] = 'B';

    for(int i = 0; i < m; ++i)
        cout << ans[i];
    cout << "\n";
}

Compilation message (stderr)

oneway.cpp: In function 'int cycle(int, int)':
oneway.cpp:105:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [to, idx]: adjacent[node]){
              ^

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