Submission #132340

#	Time	Username	Problem	Language	Result	Execution time	Memory
132340		Bench0310	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	329 ms	33832 KiB

oneway

#include <bits/stdc++.h>

using namespace std;
const int N=100005;
const int M=100005;

vector<pair<int,int>> v[N];
vector<pair<int,int>> edges;
vector<int> depth(N,-1);
vector<vector<int>> par(N,vector<int>(18,-1));
vector<int> bridge_cnt(N,0);
vector<bool> bridge(M,0);
vector<bool> span(M,0); //span-edge
vector<int> up(N,-1); //index of edge connecting vertex i and parent of i
string res(M,'B');
vector<int> id(N,0); //id in the merged graph
vector<pair<int,int>> g[N]; //merged graph
vector<bool> done(N,0); //already directed

void dfs1(int a,int p=-1)
{
    depth[a]=(p!=-1?depth[p]+1:0);
    for(pair<int,int> t:v[a])
    {
        int to=t.first;
        if(t.second==up[a]) continue;
        if(depth[to]==-1)
        {
            span[t.second]=1;
            up[to]=t.second;
            dfs1(to,a);
            bridge_cnt[a]+=bridge_cnt[to];
        }
        else if(a!=to) bridge_cnt[a]+=((depth[a]>depth[to])?1:-1);
    }
}

void dfs2(int a,int idx)
{
    id[a]=idx;
    for(pair<int,int> t:v[a])
    {
        if(bridge[t.second]) continue;
        int to=t.first;
        if(id[to]==0) dfs2(to,idx);
    }
}

void dfs3(int a,int p=-1)
{
    depth[a]=(p!=-1?depth[p]+1:0);
    par[a][0]=p;
    for(int i=1;i<18;i++)
    {
        if(par[a][i-1]==-1) break;
        par[a][i]=par[par[a][i-1]][i-1];
    }
    for(pair<int,int> t:g[a])
    {
        int to=t.first;
        if(to==p) continue;
        up[to]=t.second;
        dfs3(to,a);
    }
}

int lca(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);
    for(int i=17;i>=0;i--)
    {
        if(par[a][i]!=-1&&depth[par[a][i]]>=depth[b])
        {
            a=par[a][i];
        }
    }
    if(a==b) return a;
    for(int i=17;i>=0;i--)
    {
        if(par[a][i]!=-1&&par[b][i]!=-1&&par[a][i]!=par[b][i])
        {
            a=par[a][i];
            b=par[b][i];
        }
    }
    return par[a][0];
}

void solve(int a,int b,bool dir) //0-up,1-down
{
    int now=depth[b]-depth[a];
    if(now==0||done[a]) return;
    int c=a;
    int d=par[a][0];
    if(dir) swap(c,d);
    if(c==id[edges[up[a]].first]) res[up[a]]='R';
    else res[up[a]]='L';
    done[a]=1;
    solve(par[a][0],b,dir);
}

int main()
{
    //Graph input
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        v[a].push_back(make_pair(b,i));
        v[b].push_back(make_pair(a,i));
        edges.push_back(make_pair(a,b));
    }
    //Initialize
    for(int i=1;i<=n;i++) if(depth[i]==-1) dfs1(i,-1);
    //Find bridges
    for(int i=0;i<m;i++)
    {
        int a,b;
        tie(a,b)=edges[i];
        if(depth[a]<depth[b]) swap(a,b);
        if(span[i]&&bridge_cnt[a]==0) bridge[i]=1;
    }
    //Merge cycles
    int num=1;
    for(int i=0;i<m;i++)
    {
        if(bridge[i])
        {
            int a,b;
            tie(a,b)=edges[i];
            if(id[a]==0) dfs2(a,num++);
            if(id[b]==0) dfs2(b,num++);
        }
    }
    //Build merged graph
    for(int i=0;i<m;i++)
    {
        if(bridge[i])
        {
            int a,b;
            tie(a,b)=edges[i];
            g[id[a]].push_back(make_pair(id[b],i));
            g[id[b]].push_back(make_pair(id[a],i));
        }
    }
    //Set up merged graph
    fill(depth.begin(),depth.end(),-1);
    fill(up.begin(),up.end(),-1);
    for(int i=1;i<num;i++) if(depth[i]==-1) dfs3(i,-1);
    //Solve
    int z;
    scanf("%d",&z);
    vector<pair<int,int>> q;
    vector<pair<int,int>> one;
    vector<int> two;
    for(int i=0;i<z;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        a=id[a];
        b=id[b];
        int c=lca(a,b);
        q.push_back(make_pair(depth[c],i));
        one.push_back(make_pair(a,b));
        two.push_back(c);
    }
    sort(q.begin(),q.end());
    for(int i=0;i<z;i++)
    {
        int now=q[i].second;
        solve(one[now].first,two[now],0);
        solve(one[now].second,two[now],1);
    }
    for(int i=0;i<m;i++) printf("%c",res[i]);
    printf("\n");
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
oneway.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~
oneway.cpp:154:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&z);
     ~~~~~^~~~~~~~~
oneway.cpp:161:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

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