Submission #124896

#	Time	Username	Problem	Language	Result	Execution time	Memory
124896		semiauto	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	6 ms	5112 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],sum[100001],sumparent[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 a,int b) {
    int c=a,i;
    if (isp(c,b))
        return c;
    for (i=16;i>=0;i--)
        if (p[c][i] && !isp(p[c][i],b))
            c=p[c][i];
    return c;
}
void gogo(int a,int b) {
    int i;
    for (i=0;i<gr[a].size();i++)
        if (gr[a][i].first!=b) {
            sum[gr[a][i].first]+=sum[a]+sumparent[a];
            if (sum[gr[a][i].first]!=0) {
                int hey=mymap[{gr[a][i].second.first,gr[a][i].second.second}];
                if (sum[gr[a][i].first]>0)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 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)) {
            who=lca(a,b);
            sum[who]++;
            sumparent[a]--;
        }
        if (!isp(b,a)) {
            who=lca(b,a);
            sum[who]--;
            sumparent[b]++;
        }
    }
    gogo(1,0);
    for (i=1;i<=m;i++) {
        if (block[mymap[{a,b}]])
            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++)
              ~^~~~~~~~~~~~~

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