oj.uz

Submission #987070

# Submission time Handle Problem Language Result Execution time Memory
987070 2024-05-21T19:21:51 Z AverageAmogusEnjoyer One-Way Streets (CEOI17_oneway) C++17
100 / 100
 124 ms 41076 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
template<class T> bool cmin(T &i,T j) { return i > j ? i = j,true: false; }
template<class T> bool cmax(T &i,T j) { return i < j ? i = j,true: false; }

struct RMQ {
    int n;
    int lg;
    vector<vector<int>> sparse;
    RMQ() {}
    RMQ(vector<int> a) {
        if (a.empty()) { return; }
        n = (int)a.size();
        lg = 0;
        while((1<<lg) <= n) { lg++; }
        sparse.assign(lg,vector<int>(n));
        sparse[0] = a;
        for (int pw=1;pw<lg;pw++) {
            for (int i=0;i<n;i++) {
                sparse[pw][i] = min(sparse[pw-1][i],sparse[pw-1][min(i+(1<<(pw-1)),n-1)]);
            }
        }
    }
    int qry(int l,int r) {
        assert(0 <= l && l <= r && r < n);
        int bit = 31-__builtin_clz(r-l+1);
        return min(sparse[bit][l],sparse[bit][r-(1<<bit)+1]);
    }
};

struct LCA {
    int n;
    vector<vector<pair<int,int>>> adj;
    vector<bool> vst;
    vector<int> tin,where;
    vector<vector<int>> path,ret;
    // modify this to allow query on forest
    vector<RMQ> rmq;
    int timer = 0;
    LCA(int N,vector<vector<pair<int,int>>> a) {
        adj = a;
        n = N;
        tin.resize(n);
        where.resize(n);
        vst.assign(n,false);
        for (int x=0;x<n;x++) if (!vst[x]) {
            timer = 0;
            path.emplace_back();
            ret.emplace_back();
            dfs(x,-1);
            rmq.push_back(RMQ(ret.back()));
        }
    }
    void dfs(int x,int z) {
        tin[x] = timer++;
        assert(!vst[x]);
        vst[x] = true;
        where[x] = (int)path.size() - 1;
        for (auto &[y,idx]: adj[x]) if (y != z) {
            path.back().push_back(x),ret.back().push_back(tin[x]);
            dfs(y,x);
        }
    }
    int lca(int x,int y) { 
        if (x == y) { return x; }
        assert(where[x] == where[y]);
        if (tin[x] > tin[y]) { swap(x,y); }
        return path[where[x]][rmq[where[x]].qry(tin[x],tin[y]-1)];
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    string ans(m,'B');
    vector<vector<pair<int,int>>> adj(n);
    vector<pair<int,int>> edges(m);
    for (int i=0,x,y;i<m;i++) {
        cin >> x >> y;
        --x,--y;
        edges[i] = make_pair(x,y);
        adj[x].emplace_back(y,i);
        adj[y].emplace_back(x,i);
    }
    vector<vector<pair<int,int>>> tree(n);
    // vector<vector<pair<int,int>>> back_edges(n);
    vector<int> dp(n);
    vector<int> t(n,-1);
    int timer = 0;
    vector<bool> vst(n);
    vector<int> par(n);
    auto dfs = [&](auto &self,int x,int z) -> void {
        t[x] = timer++;
        vst[x]=true;
        par[x]=z;
        for (auto &[y,idx]: adj[x]) if (y != z) {
            if (t[y] > t[x]) {
                // back_edges[y].emplace_back(x,idx);
                // cout << "back edge: " << y+1 << " " << x+1 << endl;
                dp[y]++;
                dp[x]--;
            } else if (t[y] == -1) {
                tree[x].emplace_back(y,idx);
                tree[y].emplace_back(x,idx);
                // cout << "span edge: " << x+1 << " " << y+1 << endl;
                self(self,y,x);
            }
        }
    };
    vst.assign(n,false);
    for (int x=0;x<n;x++) if (!vst[x]) { 
        dfs(dfs,x,-1);
    }
    auto dfstree = [&](auto &self,int x,int z) -> void {
        vst[x]=true;
        for (auto &[y,idx]: tree[x]) if (y != z) {
            self(self,y,x);
            dp[x] += dp[y];
        }
    };
    vst.assign(n,false);
    for (int x=0;x<n;x++) if (!vst[x]) { 
        dfstree(dfstree,x,-1);
    }
    vector<int> up(n),down(n);
    LCA tr(n,tree);
    int q;
    cin >> q;
    for (int x,y;q--;) {
        cin >> x >> y;
        --x,--y;
        int l = tr.lca(x,y);
        /*
        vst.assign(n,false);
        int cx = x;
        while(cx != -1) {
            vst[cx] = true;
            cx = par[cx];
        }
        int cy = y;
        while(!vst[cy]) {
            cy = par[cy];
            assert(cy != -1);
        }
        int l = cy;
        */
        up[x]++;
        up[l]--;
        down[y]++;
        down[l]--;
    }
    auto dfspush = [&](auto &self,int x,int z) -> void {
        vst[x]=true;
        for (auto &[y,idx]: tree[x]) if (y != z) {
            self(self,y,x);
            up[x] += up[y];
            down[x] += down[y];
        
            // actually write down edge
            if (dp[y] != 0) { continue; } 
            assert(up[y] == 0 || down[y] == 0);
            if (up[y]) {
                if (edges[idx].second == x) {
                    ans[idx] = 'R';
                } else {
                    ans[idx] = 'L';
                }
            } else if (down[y]) {
                if (edges[idx].second == y) {
                    ans[idx] = 'R';
                } else {
                    ans[idx] = 'L';
                }
            }
        }
    };
    vst.assign(n,false);
    for (int x=0;x<n;x++) if (!vst[x]) { 
        dfspush(dfspush,x,-1); 
    }
    cout << ans << endl;    
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 32 ms 11148 KB Output is correct
12 Correct 45 ms 15444 KB Output is correct
13 Correct 60 ms 22224 KB Output is correct
14 Correct 80 ms 31304 KB Output is correct
15 Correct 88 ms 33920 KB Output is correct
16 Correct 99 ms 37360 KB Output is correct
17 Correct 80 ms 38340 KB Output is correct
18 Correct 88 ms 37320 KB Output is correct
19 Correct 86 ms 39440 KB Output is correct
20 Correct 51 ms 21456 KB Output is correct
21 Correct 51 ms 21208 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 32 ms 11148 KB Output is correct
12 Correct 45 ms 15444 KB Output is correct
13 Correct 60 ms 22224 KB Output is correct
14 Correct 80 ms 31304 KB Output is correct
15 Correct 88 ms 33920 KB Output is correct
16 Correct 99 ms 37360 KB Output is correct
17 Correct 80 ms 38340 KB Output is correct
18 Correct 88 ms 37320 KB Output is correct
19 Correct 86 ms 39440 KB Output is correct
20 Correct 51 ms 21456 KB Output is correct
21 Correct 51 ms 21208 KB Output is correct
22 Correct 96 ms 38344 KB Output is correct
23 Correct 124 ms 37076 KB Output is correct
24 Correct 106 ms 37444 KB Output is correct
25 Correct 109 ms 41076 KB Output is correct
26 Correct 107 ms 38080 KB Output is correct
27 Correct 109 ms 37064 KB Output is correct
28 Correct 21 ms 4688 KB Output is correct
29 Correct 64 ms 21144 KB Output is correct
30 Correct 63 ms 21204 KB Output is correct
31 Correct 88 ms 21460 KB Output is correct
32 Correct 78 ms 27520 KB Output is correct