Submission #415178

#	Time	Username	Problem	Language	Result	Execution time	Memory
415178		A_D	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	929 ms	72440 KiB

oneway

#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define F first
#define S second
#define du long double
using namespace std;
const int N=1e5+100;
vector<int> g[N],g2[N];
set<int> st[N];
int u[N];
int v[N];
int a[N];
bool vis[N];
int tin[N];
int low[N];
int timer;
map<ii,char> mp;
map<ii,bool> bridg;
map<int,int> mp2;
int sz;
void dfs2(int v,int p) {
    vis[v] = true;
    tin[v] = low[v] = timer++;
    bool cnt=0;
    for (int to : g[v]) {
        if (to == p&&cnt==0){
            cnt=1;
            continue;
        }
        if (vis[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs2(to, v);
            low[v] = min(low[v], low[to]);
            if (low[to] > tin[v]){
                bridg[{v, to}]=1;
                bridg[{to, v}]=1;
            }
        }
    }
}
void dfs3(int u,int v)
{
    vis[u]=1;
    mp2[u]=v;
    for(auto x:g[u]){
        if(bridg[{u,x}]){
            g2[v].push_back(x);
            continue;
        }
        if(vis[x])continue;
        dfs3(x,v);
    }
}
void dfs(int u,int p)
{
    vis[u]=1;
    for(auto x:g2[u]){
        if(x==p)continue;
        dfs(x,u);
    }
    for(auto x:g2[u]){
        if(x==p)continue;
        a[u]+=a[x];
        if(a[x]==0){
            mp[{u,x}]='B';
            mp[{x,u}]='B';
        }
        if(a[x]>0){
            mp[{u,x}]='L';
            mp[{x,u}]='R';
        }
        if(a[x]<0){
            mp[{u,x}]='R';
            mp[{x,u}]='L';
        }
    }
}
void solve()
{
    memset(tin,-1,sizeof(tin));
    memset(low,-1,sizeof(low));
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
        u[i]=a;
        v[i]=b;
    }
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        dfs2(i,i);
    }
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        dfs3(i,i);
    }
    for(int i=1;i<=n;i++){
        for(auto x:g2[i]){
            st[i].insert(mp2[x]);
        }
        g2[i].clear();
        for(auto x:st[i]){
            g2[i].push_back(x);
        }
    }
    int p;
    cin>>p;
    while(p--){
        int u,v;
        cin>>u>>v;
        a[mp2[u]]++;
        a[mp2[v]]--;
    }
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        int u=mp2[i];
        if(vis[u])continue;
        dfs(u,u);
    }
  	/*
    for(int i=1;i<=n;i++){
        cout<<mp2[i]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
        cout<<i<<" : ";
        for(auto x:g2[i])cout<<x<<" ";cout<<endl;
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    */
    for(int i=1;i<=m;i++){
        int a=mp2[u[i]];
        int b=mp2[v[i]];
        if(a==b)mp[{a,a}]='B';
        cout<<mp[{a,b}];
    }
}

main()
{
    int t=1;
//    cin>>t;
    while(t--)solve();
}

Compilation message (stderr)

oneway.cpp:148:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  148 | main()
      | ^~~~

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