oj.uz

Submission #469005

# Submission time Handle Problem Language Result Execution time Memory
469005 2021-08-30T11:26:57 Z gratus907 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 406 ms 44140 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;
const int mod = 1000000007;

#define V 101010
struct DSU {
    int par[V], sz[V];
    DSU(){init(V);}
    void init(int n) {
        for (int i = 0; i<n; i++)
            par[i] = i, sz[i] = 1;
    }
    int find(int x) {
        return x == par[x] ? x : (par[x] = find(par[x]));
    }
    void unite(int x, int y){
        int u = find(x), v = find(y);
        if (u==v) return;
        par[u] = par[v];
    }
};
DSU dsu;
struct edge {
    int u, v, idx;
    bool operator==(const edge &o) {
        return idx == o.idx;
    }
    bool operator<(const edge &o) {
        return idx < o.idx;
    }
};
char ans[101010];
int n, m, p;
struct ArticulationEdge {
    int n;
    vector <edge> G[V];
    vector <edge> arts;
    int low[V], order[V];
    bool vst[V];
    int t = 0, rt = 0;
    void dfs(int r, int par) {
        vst[r] = true;
        order[r] = t++;
        low[r] = t;
        for (edge e : G[r]) {
            int nxt = e.u + e.v -r;
            if (nxt == par) continue;
            if (!vst[nxt]) {
                dfs(nxt, r);
                if (low[nxt] > order[r])
                    arts.push_back(e);
                low[r] = min(low[nxt], low[r]);
            }
            else low[r] = min(low[r], order[nxt]);
        }
    }

    void find_art_edges() {
        memset(vst, 0, sizeof(vst));
        for (int i = 1; i <= n; i++)
            if (!vst[i])
                dfs(rt = i, 0);
        sort(all(arts));
        arts.erase(unique(all(arts)), arts.end());
    }
} ART;

vector <edge> edge_list;
vector <edge> tree_edge_list;
vector <edge> T[V];
map<pii, int> edgefind;
int dep[101010];
int tpar[101010];
int updown[101010];
#define UP 100
#define DOWN 200
void find_dep(int r, int par) {
    tpar[r] = par;
    dep[r] = dep[par]+1;
    for (edge e : T[r]) {
        int nxt = dsu.find(e.u + e.v - r);
        if (dep[nxt] > 1e9) {
            find_dep(nxt, r);
        }
    }
}
int32_t main() {
    usecppio
    cin >> n >> m; ART.n = n;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        ART.G[u].push_back({u, v, i});
        ART.G[v].push_back({u, v, i});
        edge_list.push_back({u, v, i});
    }
    ART.find_art_edges();
    for (edge e : ART.arts) {
        ans[e.idx] = 1;
    }
    for (int i = 0; i < m; i++) {
        if (!ans[i]) {
            edge e = edge_list[i];
            dsu.unite(e.u, e.v);
            ans[i] = 'B';
        }
        else ans[i] = 0;
    }
    for (edge e : edge_list) {
        if (ans[e.idx] == 0) {
            int u = dsu.find(e.u);
            int v = dsu.find(e.v);
            tree_edge_list.push_back({u, v, e.idx});
            T[u].push_back({u, v, e.idx});
            T[v].push_back({u, v, e.idx});
            edgefind[{u, v}] = e.idx;
            //printf("EDGE %lld : {%lld, %lld}\n",e.idx, u, v);
        }
    }
    /*for (int i = 0; i < m; i++) {
        if (ans[i] == 'B') cout << ans[i];
        else {
            cout << '?';
        }
    }
    cout << '\n';*/
    memset(dep, 0x7f, sizeof(dep));
    for (int i = 1; i <= n; i++) {
        if (dep[dsu.find(i)] > 1e9) {
            dep[0] = -1;
            //printf("TREE ROOT AT %lld\n",dsu.find(i));
            find_dep(dsu.find(i), 0);
        }
    }

/*
    for (int i = 1; i <= n; i++) {
        if (dep[i] < 1e9) {
            printf("Depth of %lld = %lld\n",i,dep[i]);
        }
    }*/

    cin >> p;
    while(p--) {
        int u, v; cin >> u >> v;
        u = dsu.find(u); v = dsu.find(v);
        //printf("WANTED %lld=>%lld\n",u,v);
        if (u == v) {
            continue;
        }
        else {
            while(dsu.find(u) != dsu.find(v)) {
                u = dsu.find(u); v = dsu.find(v);
                if (dep[u] > dep[v]) {
                    //printf("%lld->%lld(%lld)\n",u,tpar[u],dsu.find(tpar[u]));
                    //printf("UPDOWN %lld = UP\n",u);
                    updown[u] = UP;
                    if (edgefind.find({u, tpar[u]}) != edgefind.end()) {
                        int idx = edgefind[{u, tpar[u]}];
                        ans[idx] = 'R';
                    }
                    else {
                        int idx = edgefind[{tpar[u], u}];
                        ans[idx] = 'L';
                    }
                    dsu.unite(u, tpar[u]);
                }
                else {
                    //printf("%lld(%lld)->%lld\n",tpar[v],dsu.find(tpar[v]),v);
                    updown[v] = DOWN;
                    //printf("UPDOWN %lld = DOWN\n",v);
                    if (edgefind.find({tpar[v], v}) != edgefind.end()) {
                        int idx = edgefind[{tpar[v], v}];
                        ans[idx] = 'R';
                    }
                    else {
                        int idx = edgefind[{v, tpar[v]}];
                        ans[idx] = 'L';
                    }
                    dsu.unite(v, tpar[v]);
                }
            }
        }
    }

    for (int i = 0; i < m; i++) {
        if (ans[i] == '?' || ans[i] == 0) ans[i] = 'B';
        cout << ans[i];
    }
    cout << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7520 KB Output is correct
2 Correct 4 ms 7568 KB Output is correct
3 Correct 4 ms 7684 KB Output is correct
4 Correct 5 ms 7812 KB Output is correct
5 Correct 5 ms 7816 KB Output is correct
6 Correct 6 ms 7628 KB Output is correct
7 Correct 5 ms 7828 KB Output is correct
8 Correct 5 ms 7756 KB Output is correct
9 Correct 5 ms 7628 KB Output is correct
10 Correct 5 ms 7628 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7520 KB Output is correct
2 Correct 4 ms 7568 KB Output is correct
3 Correct 4 ms 7684 KB Output is correct
4 Correct 5 ms 7812 KB Output is correct
5 Correct 5 ms 7816 KB Output is correct
6 Correct 6 ms 7628 KB Output is correct
7 Correct 5 ms 7828 KB Output is correct
8 Correct 5 ms 7756 KB Output is correct
9 Correct 5 ms 7628 KB Output is correct
10 Correct 5 ms 7628 KB Output is correct
11 Correct 63 ms 19876 KB Output is correct
12 Correct 75 ms 21100 KB Output is correct
13 Correct 94 ms 22336 KB Output is correct
14 Correct 111 ms 25584 KB Output is correct
15 Correct 136 ms 27276 KB Output is correct
16 Correct 205 ms 37768 KB Output is correct
17 Correct 209 ms 39912 KB Output is correct
18 Correct 244 ms 38384 KB Output is correct
19 Correct 200 ms 41132 KB Output is correct
20 Correct 67 ms 19944 KB Output is correct
21 Correct 60 ms 20548 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7520 KB Output is correct
2 Correct 4 ms 7568 KB Output is correct
3 Correct 4 ms 7684 KB Output is correct
4 Correct 5 ms 7812 KB Output is correct
5 Correct 5 ms 7816 KB Output is correct
6 Correct 6 ms 7628 KB Output is correct
7 Correct 5 ms 7828 KB Output is correct
8 Correct 5 ms 7756 KB Output is correct
9 Correct 5 ms 7628 KB Output is correct
10 Correct 5 ms 7628 KB Output is correct
11 Correct 63 ms 19876 KB Output is correct
12 Correct 75 ms 21100 KB Output is correct
13 Correct 94 ms 22336 KB Output is correct
14 Correct 111 ms 25584 KB Output is correct
15 Correct 136 ms 27276 KB Output is correct
16 Correct 205 ms 37768 KB Output is correct
17 Correct 209 ms 39912 KB Output is correct
18 Correct 244 ms 38384 KB Output is correct
19 Correct 200 ms 41132 KB Output is correct
20 Correct 67 ms 19944 KB Output is correct
21 Correct 60 ms 20548 KB Output is correct
22 Correct 312 ms 41068 KB Output is correct
23 Correct 310 ms 39532 KB Output is correct
24 Correct 406 ms 39432 KB Output is correct
25 Correct 299 ms 44140 KB Output is correct
26 Correct 313 ms 40680 KB Output is correct
27 Correct 346 ms 39660 KB Output is correct
28 Correct 49 ms 17276 KB Output is correct
29 Correct 82 ms 20720 KB Output is correct
30 Correct 80 ms 21216 KB Output is correct
31 Correct 98 ms 20988 KB Output is correct
32 Correct 135 ms 31084 KB Output is correct