Submission #1027194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027194		KhoaDuy	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	157 ms	67412 KiB

oneway

#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 (stderr)

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