Submission #987070

#	Time	Username	Problem	Language	Result	Execution time	Memory
987070		AverageAmogusEnjoyer	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	124 ms	41076 KiB

oneway

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40