oj.uz

Submission #124976

# Submission time Handle Problem Language Result Execution time Memory
124976 2019-07-04T08:53:03 Z semiauto One-Way Streets (CEOI17_oneway) C++14
100 / 100
 919 ms 43256 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 8 ms 5240 KB Output is correct
4 Correct 9 ms 5368 KB Output is correct
5 Correct 9 ms 5368 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 9 ms 5368 KB Output is correct
8 Correct 9 ms 5368 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 8 ms 5240 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 8 ms 5240 KB Output is correct
4 Correct 9 ms 5368 KB Output is correct
5 Correct 9 ms 5368 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 9 ms 5368 KB Output is correct
8 Correct 9 ms 5368 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 8 ms 5240 KB Output is correct
11 Correct 406 ms 23396 KB Output is correct
12 Correct 453 ms 24640 KB Output is correct
13 Correct 669 ms 26488 KB Output is correct
14 Correct 612 ms 31224 KB Output is correct
15 Correct 645 ms 33556 KB Output is correct
16 Correct 656 ms 36736 KB Output is correct
17 Correct 582 ms 38468 KB Output is correct
18 Correct 703 ms 36860 KB Output is correct
19 Correct 577 ms 39800 KB Output is correct
20 Correct 428 ms 23920 KB Output is correct
21 Correct 364 ms 23288 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 8 ms 5240 KB Output is correct
4 Correct 9 ms 5368 KB Output is correct
5 Correct 9 ms 5368 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 9 ms 5368 KB Output is correct
8 Correct 9 ms 5368 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 8 ms 5240 KB Output is correct
11 Correct 406 ms 23396 KB Output is correct
12 Correct 453 ms 24640 KB Output is correct
13 Correct 669 ms 26488 KB Output is correct
14 Correct 612 ms 31224 KB Output is correct
15 Correct 645 ms 33556 KB Output is correct
16 Correct 656 ms 36736 KB Output is correct
17 Correct 582 ms 38468 KB Output is correct
18 Correct 703 ms 36860 KB Output is correct
19 Correct 577 ms 39800 KB Output is correct
20 Correct 428 ms 23920 KB Output is correct
21 Correct 364 ms 23288 KB Output is correct
22 Correct 798 ms 39744 KB Output is correct
23 Correct 919 ms 37756 KB Output is correct
24 Correct 813 ms 38008 KB Output is correct
25 Correct 847 ms 43256 KB Output is correct
26 Correct 810 ms 39184 KB Output is correct
27 Correct 810 ms 38140 KB Output is correct
28 Correct 204 ms 7972 KB Output is correct
29 Correct 524 ms 24696 KB Output is correct
30 Correct 492 ms 24684 KB Output is correct
31 Correct 562 ms 25300 KB Output is correct
32 Correct 568 ms 29728 KB Output is correct