oj.uz

Submission #908669

# Submission time Handle Problem Language Result Execution time Memory
908669 2024-01-16T16:19:39 Z asdasdqwer One-Way Streets (CEOI17_oneway) C++14
100 / 100
 306 ms 42120 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 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 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 39 ms 5572 KB Output is correct
12 Correct 29 ms 7108 KB Output is correct
13 Correct 41 ms 9928 KB Output is correct
14 Correct 58 ms 17240 KB Output is correct
15 Correct 63 ms 20092 KB Output is correct
16 Correct 104 ms 33556 KB Output is correct
17 Correct 132 ms 36172 KB Output is correct
18 Correct 90 ms 33844 KB Output is correct
19 Correct 122 ms 37936 KB Output is correct
20 Correct 37 ms 8644 KB Output is correct
21 Correct 50 ms 8252 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 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 39 ms 5572 KB Output is correct
12 Correct 29 ms 7108 KB Output is correct
13 Correct 41 ms 9928 KB Output is correct
14 Correct 58 ms 17240 KB Output is correct
15 Correct 63 ms 20092 KB Output is correct
16 Correct 104 ms 33556 KB Output is correct
17 Correct 132 ms 36172 KB Output is correct
18 Correct 90 ms 33844 KB Output is correct
19 Correct 122 ms 37936 KB Output is correct
20 Correct 37 ms 8644 KB Output is correct
21 Correct 50 ms 8252 KB Output is correct
22 Correct 190 ms 37800 KB Output is correct
23 Correct 233 ms 34776 KB Output is correct
24 Correct 172 ms 34748 KB Output is correct
25 Correct 306 ms 42120 KB Output is correct
26 Correct 292 ms 36576 KB Output is correct
27 Correct 252 ms 35416 KB Output is correct
28 Correct 24 ms 3532 KB Output is correct
29 Correct 58 ms 9044 KB Output is correct
30 Correct 60 ms 9056 KB Output is correct
31 Correct 52 ms 9888 KB Output is correct
32 Correct 90 ms 19912 KB Output is correct