oj.uz

Submission #1027223

# Submission time Handle Problem Language Result Execution time Memory
1027223 2024-07-19T02:14:06 Z vjudge1 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 143 ms 66640 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int MAXN=2*1e5;
int comp[MAXN+1]={0};
int tim=1;
int low[MAXN+1];
int in[MAXN+1]={0};
int mark[MAXN+1]={0};
vector<vector<int>> graph(MAXN+1);
vector<vector<int>> idx(MAXN+1);
char ans[MAXN+1];
int cc=0;
stack<int> st;
void DFS(int u,int p){
    in[u]=tim;
    low[u]=tim;
    tim++;
    bool skip=false;
    st.push(u);
    for(int i=0;i<graph[u].size();i++){
        int v=graph[u][i];
        if(v==p&&!skip){
            skip=true;
            continue;
        }
        if(!in[v]){
            DFS(v,u);
            low[u]=min(low[u],low[v]);
            if(in[u]<low[v]){
                while(st.top()!=v){
                    comp[st.top()]=cc;
                    st.pop();
                }
                comp[st.top()]=cc;
                st.pop();
                cc++;
            }
            else{
                ans[idx[u][i]]='B';
            }
        }
        else{
            ans[idx[u][i]]='B';
            low[u]=min(low[u],in[v]);
        }
    }
}
int lift[19][MAXN+1];
int depth[MAXN+1];
void setup(int u,int p,int idx){
    lift[0][u]=p;
    mark[u]=idx;
    for(int i=1;i<19;i++){
        lift[i][u]=lift[i-1][lift[i-1][u]];
    }
    for(int i=0;i<graph[u].size();i++){
        int v=graph[u][i];
        if(v!=p){
            depth[v]=depth[u]+1;
            setup(v,u,idx);
        }
    }
}
int a[MAXN+1]={0};
int b[MAXN+1]={0};
int c[MAXN+1]={0};
int LCA(int u,int v){
    if(depth[u]<depth[v]){
        swap(u,v);
    }
    for(int i=18;i>=0;i--){
        if((depth[u]-depth[v])&(1<<i)){
            u=lift[i][u];
        }
    }
    if(u==v){
        return u;
    }
    for(int i=18;i>=0;i--){
        if(lift[i][u]!=lift[i][v]){
            u=lift[i][u];
            v=lift[i][v];
        }
    }
    return lift[0][u];
}
bool check(int u,int p){
    bool curr=true;
    for(int i=0;i<graph[u].size();i++){
        int v=graph[u][i];
        if(v!=p){
            curr&=check(v,u);
            a[u]+=a[v];
            b[u]+=b[v];
            c[u]+=c[v];
            if(a[v]==c[v]&&b[v]==c[v]){
                ans[abs(idx[u][i])-1]='B';
            }
            else if(b[v]>c[v]){
                if(idx[u][i]>0){
                    ans[abs(idx[u][i])-1]='R';
                }
                else{
                    ans[abs(idx[u][i])-1]='L';
                }
            }
            else{
                if(idx[u][i]>0){
                    ans[abs(idx[u][i])-1]='L';
                }
                else{
                    ans[abs(idx[u][i])-1]='R';
                }
            }
        }
    }
    if(a[u]>c[u]&&b[u]>c[u]){
        curr=false;
    }
    return curr;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    vector<int> root;
    int n,m,q;
    cin >> n >> m;
    vector<pair<int,int>> edges(m);
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        edges[i]={u,v};
        graph[u].push_back(v);
        graph[v].push_back(u);
        idx[u].push_back(i);
        idx[v].push_back(i);
    }
    for(int i=1;i<=n;i++){
        if(!in[i]){
            DFS(i,-1);
            root.push_back(i);
            while(!st.empty()){
                comp[st.top()]=cc;
                st.pop();
            }
            cc++;
        }
    }
    graph.clear();
    graph.resize(cc);
    idx.clear();
    idx.resize(cc);
    for(int i=0;i<m;i++){
        int u=edges[i].first,v=edges[i].second;
        if(comp[u]!=comp[v]){
            graph[comp[u]].push_back(comp[v]);
            graph[comp[v]].push_back(comp[u]);
            idx[comp[u]].push_back(i+1);
            idx[comp[v]].push_back(-(i+1));
        }
    }
    int idx=0;
    for(int i=0;i<root.size();i++){
        depth[comp[root[i]]]=0;
        setup(comp[root[i]],comp[root[i]],idx);
        idx++;
    }
    cin >> q;
    bool flag=true;
    for(int i=0;i<q;i++){
        int s,d;
        cin >> s >> d;
        if(!flag||mark[comp[s]]!=mark[comp[d]]){
            flag=false;
            continue;
        }
        int lca=LCA(comp[s],comp[d]);
        a[comp[s]]++;
        b[comp[d]]++;
        c[lca]++;
    }
    for(int i=0;i<root.size();i++){
        flag&=check(comp[root[i]],-1);
    }
    for(int i=0;i<m;i++){
        cout << ans[i];
    }
}

Compilation message

oneway.cpp: In function 'void DFS(long long int, long long int)':
oneway.cpp:22:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<graph[u].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'void setup(long long int, long long int, long long int)':
oneway.cpp:58:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0;i<graph[u].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'bool check(long long int, long long int)':
oneway.cpp:91:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i=0;i<graph[u].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:165:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |     for(int i=0;i<root.size();i++){
      |                 ~^~~~~~~~~~~~
oneway.cpp:184:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |     for(int i=0;i<root.size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 48732 KB Output is correct
2 Correct 6 ms 48732 KB Output is correct
3 Correct 6 ms 48988 KB Output is correct
4 Correct 6 ms 48732 KB Output is correct
5 Correct 7 ms 48984 KB Output is correct
6 Correct 6 ms 48732 KB Output is correct
7 Correct 7 ms 48852 KB Output is correct
8 Correct 6 ms 48968 KB Output is correct
9 Correct 6 ms 48732 KB Output is correct
10 Correct 6 ms 48728 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 48732 KB Output is correct
2 Correct 6 ms 48732 KB Output is correct
3 Correct 6 ms 48988 KB Output is correct
4 Correct 6 ms 48732 KB Output is correct
5 Correct 7 ms 48984 KB Output is correct
6 Correct 6 ms 48732 KB Output is correct
7 Correct 7 ms 48852 KB Output is correct
8 Correct 6 ms 48968 KB Output is correct
9 Correct 6 ms 48732 KB Output is correct
10 Correct 6 ms 48728 KB Output is correct
11 Correct 42 ms 57936 KB Output is correct
12 Correct 41 ms 59160 KB Output is correct
13 Correct 45 ms 60472 KB Output is correct
14 Correct 57 ms 61776 KB Output is correct
15 Correct 60 ms 62036 KB Output is correct
16 Correct 78 ms 59984 KB Output is correct
17 Correct 75 ms 62040 KB Output is correct
18 Correct 80 ms 59988 KB Output is correct
19 Correct 74 ms 63312 KB Output is correct
20 Correct 59 ms 58836 KB Output is correct
21 Correct 41 ms 58480 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 48732 KB Output is correct
2 Correct 6 ms 48732 KB Output is correct
3 Correct 6 ms 48988 KB Output is correct
4 Correct 6 ms 48732 KB Output is correct
5 Correct 7 ms 48984 KB Output is correct
6 Correct 6 ms 48732 KB Output is correct
7 Correct 7 ms 48852 KB Output is correct
8 Correct 6 ms 48968 KB Output is correct
9 Correct 6 ms 48732 KB Output is correct
10 Correct 6 ms 48728 KB Output is correct
11 Correct 42 ms 57936 KB Output is correct
12 Correct 41 ms 59160 KB Output is correct
13 Correct 45 ms 60472 KB Output is correct
14 Correct 57 ms 61776 KB Output is correct
15 Correct 60 ms 62036 KB Output is correct
16 Correct 78 ms 59984 KB Output is correct
17 Correct 75 ms 62040 KB Output is correct
18 Correct 80 ms 59988 KB Output is correct
19 Correct 74 ms 63312 KB Output is correct
20 Correct 59 ms 58836 KB Output is correct
21 Correct 41 ms 58480 KB Output is correct
22 Correct 132 ms 62500 KB Output is correct
23 Correct 127 ms 60500 KB Output is correct
24 Correct 124 ms 60496 KB Output is correct
25 Correct 133 ms 66640 KB Output is correct
26 Correct 123 ms 62004 KB Output is correct
27 Correct 143 ms 60500 KB Output is correct
28 Correct 26 ms 51392 KB Output is correct
29 Correct 54 ms 58704 KB Output is correct
30 Correct 57 ms 59072 KB Output is correct
31 Correct 53 ms 59472 KB Output is correct
32 Correct 86 ms 61788 KB Output is correct