Submission #908669

#	Time	Username	Problem	Language	Result	Execution time	Memory
908669		asdasdqwer	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	306 ms	42120 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,m;cin>>n>>m;
    vector<vector<int>> g(n);
    vector<array<int,2>> edg;
    for (int i=0;i<m;i++) {
        int a,b;cin>>a>>b;a--;b--;
        edg.push_back({a,b});
        if (a==b) continue;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    // calculate two-edge connected components

    vector<int> low(n, 1e9), num(n, 0);
    vector<vector<int>> cmp;
    int timer=0;
    stack<int> st;

    function<void(int,int)> dfs=[&](int node, int parent) {
        low[node]=num[node]=++timer;
        st.push(node);
        bool multiple = false;
        for (int x:g[node]) {
            if (x == parent && !multiple) {
                multiple = true;
                continue;
            }

            if (num[x] == 0) {
                dfs(x,node);
                low[node]=min(low[node],low[x]);
            }

            else {
                low[node]=min(low[node],num[x]);
            }
        }

        if (low[node] == num[node]) {
            cmp.push_back({});

            while (st.top() != node) {
                cmp[cmp.size()-1].push_back(st.top());
                st.pop();
            }

            cmp[cmp.size()-1].push_back(node);
            st.pop();
        }
    };

    for (int i=0;i<n;i++) {
        if (num[i]==0) dfs(i,-1);
    }

    vector<int> idx(n, -1);
    for (int i=0;i<cmp.size();i++) {
        for (int x:cmp[i]) {
            idx[x]=i;
        }
    }

    vector<vector<int>> tree(cmp.size());
    for (int i=0;i<n;i++) {
        for (int x:g[i]) {
            if (idx[x] != idx[i]) {
                tree[idx[i]].push_back(idx[x]);
            }
        }
    }

    n=cmp.size();

    vector<int> p(n,-1), d(n,0);

    function<void(int,int)> dfs2=[&](int node, int parent) {
        for (int x:tree[node]) {
            if (x==parent)continue;
            else if (p[x] != -1) continue;
            p[x]=node;
            d[x]=d[node]+1;
            dfs2(x,node);
        }
    };

    for (int i=0;i<n;i++) {
        if (p[i]==-1)dfs2(i,-1);
    }

    vector<vector<int>> lft(n, vector<int>(20));
    for (int i=0;i<n;i++) {
        lft[i][0]=p[i];
    }

    for (int j=1;j<20;j++) {
        for (int i=0;i<n;i++) {
            lft[i][j]=lft[i][j-1];
            if (lft[i][j] != -1) {
                lft[i][j]=lft[lft[i][j]][j-1];
            }
        }
    }

    function<int(int,int)> jmp=[&](int a, int steps)->int{
        int cnt=0;
        while (steps) {
            if ((steps&1)==1) {
                a=lft[a][cnt];
                if (a==-1)return -1;
            }
            steps>>=1;
            cnt++;
        }
        return a;
    };

    function<int(int,int)> lca=[&](int a, int b) -> int {
        if (d[a]<d[b])swap(a,b);
        a=jmp(a,d[a]-d[b]);
        if (a==b)return a;

        for (int i=19;i>=0;i--) {
            if (lft[a][i] != lft[b][i]) {
                a=lft[a][i];
                b=lft[b][i];
            }
        }
        return lft[a][0];
    };

    int t;cin>>t;
    vector<int> up(n, 0), down(n, 0);

    for (int i=0;i<t;i++) {
        int a,b;cin>>a>>b;a--;b--;
        a=idx[a];b=idx[b];
        if (a==b)continue;
        int l=lca(a,b);

        if (l == a) {
            down[b]++;
            down[a]--;
        }

        else if (l == b) {
            up[b]--;
            up[a]++;
        }

        else {
            up[a]++;
            down[b]++;
            up[l]--;
            down[l]--;
        }
    }

    vector<bool> vis(n, false);

    function<void(int,int)> dfs3=[&](int node, int pv) {
        vis[node]=true;
        for (int x:tree[node]) {
            if (x==pv)continue;
            dfs3(x,node);
        }

        for (int x:tree[node]) {
			if (x==pv)continue;
            up[node]+=up[x];
            down[node]+=down[x];
        }
    };

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

    for (auto x:edg) {
        x[0]=idx[x[0]];
        x[1]=idx[x[1]];
        if (x[0]==x[1]) {
            cout<<"B";
            continue;
        }
        
        else if (d[x[0]] < d[x[1]]) {
            if (up[x[1]] == 0 && down[x[1]] == 0) {
                cout<<"B";
            }

            else if (up[x[1]] > down[x[1]]) {
                cout<<"L";
            }

            else {
                cout<<"R";
            }
        }

        else {
            if (up[x[0]] == 0 && down[x[0]] == 0) {
                cout<<"B";
            }

            else if (up[x[0]] > down[x[0]]) {
                cout<<"R";
            }

            else {
                cout<<"L";
            }
        }
    }

    cout<<"\n";
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i=0;i<cmp.size();i++) {
      |                  ~^~~~~~~~~~~

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