oj.uz

Submission #908652

# Submission time Handle Problem Language Result Execution time Memory
908652 2024-01-16T15:57:12 Z asdasdqwer One-Way Streets (CEOI17_oneway) C++14
30 / 100
 109 ms 22468 KB 
#include <bits/stdc++.h>
using namespace std;

signed main() {
    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 biconnected 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());
    vector<vector<int>> child(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;
            p[x]=node;
            d[x]=d[node]+1;
            child[node].push_back(x);
            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]--;
        }
    }

    function<void(int,int)> dfs3=[&](int node, int pv) {
        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];
        }
    };

    dfs3(0, -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:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     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 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 56 ms 6600 KB Output is correct
12 Correct 58 ms 8132 KB Output is correct
13 Correct 64 ms 11288 KB Output is correct
14 Correct 78 ms 19164 KB Output is correct
15 Incorrect 109 ms 22468 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 56 ms 6600 KB Output is correct
12 Correct 58 ms 8132 KB Output is correct
13 Correct 64 ms 11288 KB Output is correct
14 Correct 78 ms 19164 KB Output is correct
15 Incorrect 109 ms 22468 KB Output isn't correct
16 Halted 0 ms 0 KB -