Submission #124976

#	Time	Username	Problem	Language	Result	Execution time	Memory
124976		semiauto	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	919 ms	43256 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
int n,m,a,b,t,i,who,k,q;
char ch[100001];
vector <int> v[100001];
vector <pair <int,pair <int,int> > > gr[100001];
bool fix[100001],block[100001],isbridge[100001];
int tin[100001],low[100001],parent[100001],in[100001],out[100001],aloup[100001],alodown[100001],A[100001],B[100001],p[100001][17];
map <pair<int,int>,int> mymap;
void dfsjust(int a,int c) {
    parent[a]=c;
    int i;
    for (i=0;i<v[a].size();i++) {
        if (parent[v[a][i]] && parent[v[a][i]]!=c && isbridge[mymap[{a,v[a][i]}]]) {
            gr[c].push_back({parent[v[a][i]],{a,v[a][i]}});
            gr[parent[v[a][i]]].push_back({c,{v[a][i],a}});
        }
        if (!parent[v[a][i]] && !isbridge[mymap[{a,v[a][i]}]])
            dfsjust(v[a][i],c);
    }
}
void justdfs(int a) {
    fix[a]=1;
    int i;
    for (i=0;i<v[a].size();i++)
        if (!fix[v[a][i]])
            justdfs(v[a][i]);
}
void dfs(int a,int b) {
    fix[a]=1;
    tin[a]=low[a]=t++;
    int i;
    for (i=0;i<v[a].size();i++) {
        if (v[a][i]==b)
            continue;
        if (fix[v[a][i]])
            low[a]=min(low[a],tin[v[a][i]]);
        else {
            dfs(v[a][i],a);
            low[a]=min(low[a],low[v[a][i]]);
            if (low[v[a][i]]>tin[a])
                isbridge[mymap[{a,v[a][i]}]]=1;
        }
    }
}
void go(int a,int b) {
    in[a]=t++;
    p[a][0]=b;
    int i;
    for (i=1;i<17;i++)
        p[a][i]=p[p[a][i-1]][i-1];
    for (i=0;i<gr[a].size();i++)
        if (gr[a][i].first!=b)
            go(gr[a][i].first,a);
    out[a]=t++;
}
bool isp(int a,int b) {
    if (in[a]<=in[b] && out[a]>=out[b])
        return true;
    return false;
}
int lca(int c,int b) {
    int x=1,i;
    for (i=16;i>=0;i--)
        if (p[c][i] && !isp(p[c][i],b)) {
            c=p[c][i];
            x+=(1<<i);
        }
    return x;
}
void gogo(int a,int b) {
    int i;
    for (i=0;i<gr[a].size();i++)
        if (gr[a][i].first!=b) {
            if (aloup[gr[a][i].first] || alodown[gr[a][i].first]) {
                int hey=mymap[{gr[a][i].second.first,gr[a][i].second.second}];
                if (aloup[gr[a][i].first])
                    swap(A[hey],B[hey]);
                if (gr[a][i].second.second==B[hey])
                    ch[hey]='R';
                else
                    ch[hey]='L';

            }
            gogo(gr[a][i].first,a);
    }
}
int goup(int a,int b) {
    int i,x=0;
    for (i=0;i<gr[a].size();i++)
        if (gr[a][i].first!=b)
            x=max(x,goup(gr[a][i].first,a));
    return aloup[a]=max(aloup[a],x-1);
}
int godown(int a,int b) {
    int i,x=0;
    for (i=0;i<gr[a].size();i++)
        if (gr[a][i].first!=b)
            x=max(x,godown(gr[a][i].first,a));
    return alodown[a]=max(alodown[a],x-1);
}
int main() {
    cin>>n>>m;
    for (i=1;i<=m;i++) {
        ch[i]='B';
        cin>>a>>b;
        A[i]=a;B[i]=b;
        if (a==b)
            continue;
        if (mymap[{a,b}])
            block[mymap[{a,b}]]=block[mymap[{b,a}]]=1;
        else {
            v[a].push_back(b);
            v[b].push_back(a);
            mymap[{a,b}]=mymap[{b,a}]=i;
        }
    }
    for (i=1;i<=n;i++) {
        if (!fix[i])
            justdfs(i);
        else
            continue;
        if (who) {
            v[who].push_back(i);
            v[i].push_back(who);
        }
        else
            who=i;
    }
    for (i=1;i<=n;i++)
        fix[i]=0;
    for (i=1;i<=n;i++)
        if (!fix[i])
            dfs(i,-1);
    for (i=1;i<=n;i++)
        if (!parent[i])
            dfsjust(i,++k);
    go(1,0);
    cin>>q;
    for (i=1;i<=q;i++) {
        cin>>a>>b;
        a=parent[a];
        b=parent[b];
        if (!isp(a,b))
            aloup[a]=max(aloup[a],lca(a,b));
        if (!isp(b,a))
            alodown[b]=max(alodown[b],lca(b,a));
    }
    aloup[1]=goup(1,0);
    alodown[1]=godown(1,0);
    gogo(1,0);
    for (i=1;i<=m;i++) {
        if (block[mymap[{A[i],B[i]}]])
            ch[i]='B';
        cout<<ch[i];
    }
    cout<<endl;
}

Compilation message (stderr)

oneway.cpp: In function 'void dfsjust(int, int)':
oneway.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[a].size();i++) {
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void justdfs(int)':
oneway.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[a].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[a].size();i++) {
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void go(int, int)':
oneway.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<gr[a].size();i++)
              ~^~~~~~~~~~~~~
oneway.cpp: In function 'void gogo(int, int)':
oneway.cpp:73:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<gr[a].size();i++)
              ~^~~~~~~~~~~~~
oneway.cpp: In function 'int goup(int, int)':
oneway.cpp:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<gr[a].size();i++)
              ~^~~~~~~~~~~~~
oneway.cpp: In function 'int godown(int, int)':
oneway.cpp:97:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<gr[a].size();i++)
              ~^~~~~~~~~~~~~

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