oj.uz

Submission #340075

# Submission time Handle Problem Language Result Execution time Memory
340075 2020-12-26T19:25:59 Z lukameladze One-Way Streets (CEOI17_oneway) C++14
100 / 100
 836 ms 78384 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=2e5+5;
long long u,vv,n,m,t,lc,a[N],out[N],lv[N],b[N],fix[N],in[N],tin,p[N][20],low[N],brd[N];
vector < pair <long long, long long > > v[N];
map < pair < int, int >, int > ind;

long long pa[N];
map < pair <long long, long long > , long long> ans,brdg;
char ch[N];
int get_col(int a)
{
    if (a==pa[a]) return a;
    return pa[a]=get_col(pa[a]);
}
void dfs(int a, int b)
{
    fix[a]=1;
    tin++;
    in[a]=low[a]=tin;
    lv[a]=lv[b]+1;
    p[a][0]=b;
    for (int i=1; i<=18; i++)
    {
        p[a][i]=p[p[a][i-1]][i-1];
    }
    for (int i=0; i<v[a].size(); i++)
    {
        if (v[a][i].f==b) continue;
        if (fix[v[a][i].f])
        {
            low[a]=min(low[a],in[v[a][i].f]);
        }
        else
        {
            dfs(v[a][i].f,a);
            low[a]=min(low[a],low[v[a][i].f]);
            if (low[v[a][i].f]>in[a])
            {
                brdg[{v[a][i].f,a}]=1;
                brdg[{a,v[a][i].f}]=1;
                brd[v[a][i].s]=1;
            }
        }
    }
    out[a]=tin;
}
bool upper (int a, int b)
{
    if (in[a]<=in[b] && out[a]>=out[b]) return true;
    else return false;
}
int lca(int a, int b)
{
    if (upper(b,a)) return b;
    for (int i=18; i>=0; i--)
    {
        if (p[b][i] && !upper(p[b][i],a))
        b=p[b][i];
    }
    return p[b][0];
}
int main()
{
    cin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        cin>>a[i]>>b[i];
        //if (a[i]==123 && b[i]==195) cout<<123<<" "<<195<<endl;
         //if (a[i]==195 && b[i]==123) cout<<123<<"   "<<195<<endl;
        v[a[i]].pb({b[i],i});
        v[b[i]].pb({a[i],i});
        
    }
  //  cout<<a[987-21]<<" "<<b[987-21]<<endl;
    for (int i=1; i<=n; i++)
    {
        if (!fix[i])
        {
            dfs(i,0);
        }
    }
    for (int i=1; i<=m; i++)
    {
        //if (a[i]==123 && b[i]==195) cout<<ind[{a[i],b[i]}]<<endl;
       // if (a[i]==195 && b[i]==123) cout<<ind[{a[i],b[i]}]<<endl;
        if (ind[{a[i],b[i]}]!=0)
        {
            brdg[{a[i], b[i]}]=brdg[{b[i],a[i]}]=0;
            brd[i]=0;
            brd[ind[{a[i],b[i]}]]=0;
        }
        ind[{a[i],b[i]}]=i;
        ind[{b[i],a[i]}]=i;
    }
    //cout<<brdg[{123,195}]<<endl;
    for (int i=1; i<=n; i++)
    {
        pa[i]=i;
    }
    cin>>t;
    while (t--)
    {
        cin>>u>>vv;
        lc=lca(u,vv);
        u=get_col(u);
        while (lv[u]>lv[lc])
        {
            if (brdg[{u,p[u][0]}] || brdg[{p[u][0],u}]) 
            {
                ans[{u,p[u][0]}]=1;
            }
            pa[u]=p[u][0];
            u=get_col(u);
        }
        vv=get_col(vv);
        while (lv[vv]>lv[lc])
        {
            if (brdg[{vv,p[vv][0]}] || brdg[{p[vv][0],vv}]) ans[{p[vv][0],vv}]=1;
            pa[vv]=p[vv][0];
            vv=get_col(vv);
        }
    }
    for (int i=1; i<=m; i++)
    {
        if (!brd[i]) 
        {
            cout<<"B";
            continue;
        }
        if (ans[{a[i],b[i]}]==1) cout<<"R";
        else if (ans[{b[i],a[i]}]==1) cout<<"L";
        else cout<<"B";
    }
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i=0; i<v[a].size(); i++)
      |                   ~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 5 ms 5484 KB Output is correct
4 Correct 6 ms 5740 KB Output is correct
5 Correct 6 ms 5740 KB Output is correct
6 Correct 5 ms 5484 KB Output is correct
7 Correct 6 ms 5740 KB Output is correct
8 Correct 6 ms 5740 KB Output is correct
9 Correct 5 ms 5484 KB Output is correct
10 Correct 5 ms 5484 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 5 ms 5484 KB Output is correct
4 Correct 6 ms 5740 KB Output is correct
5 Correct 6 ms 5740 KB Output is correct
6 Correct 5 ms 5484 KB Output is correct
7 Correct 6 ms 5740 KB Output is correct
8 Correct 6 ms 5740 KB Output is correct
9 Correct 5 ms 5484 KB Output is correct
10 Correct 5 ms 5484 KB Output is correct
11 Correct 294 ms 32876 KB Output is correct
12 Correct 335 ms 38124 KB Output is correct
13 Correct 358 ms 45364 KB Output is correct
14 Correct 399 ms 55916 KB Output is correct
15 Correct 412 ms 59244 KB Output is correct
16 Correct 581 ms 71788 KB Output is correct
17 Correct 554 ms 73452 KB Output is correct
18 Correct 593 ms 71916 KB Output is correct
19 Correct 539 ms 75500 KB Output is correct
20 Correct 277 ms 40684 KB Output is correct
21 Correct 251 ms 39768 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 5 ms 5484 KB Output is correct
4 Correct 6 ms 5740 KB Output is correct
5 Correct 6 ms 5740 KB Output is correct
6 Correct 5 ms 5484 KB Output is correct
7 Correct 6 ms 5740 KB Output is correct
8 Correct 6 ms 5740 KB Output is correct
9 Correct 5 ms 5484 KB Output is correct
10 Correct 5 ms 5484 KB Output is correct
11 Correct 294 ms 32876 KB Output is correct
12 Correct 335 ms 38124 KB Output is correct
13 Correct 358 ms 45364 KB Output is correct
14 Correct 399 ms 55916 KB Output is correct
15 Correct 412 ms 59244 KB Output is correct
16 Correct 581 ms 71788 KB Output is correct
17 Correct 554 ms 73452 KB Output is correct
18 Correct 593 ms 71916 KB Output is correct
19 Correct 539 ms 75500 KB Output is correct
20 Correct 277 ms 40684 KB Output is correct
21 Correct 251 ms 39768 KB Output is correct
22 Correct 775 ms 72940 KB Output is correct
23 Correct 758 ms 69996 KB Output is correct
24 Correct 809 ms 70052 KB Output is correct
25 Correct 836 ms 78384 KB Output is correct
26 Correct 793 ms 72248 KB Output is correct
27 Correct 772 ms 70252 KB Output is correct
28 Correct 192 ms 13548 KB Output is correct
29 Correct 430 ms 44396 KB Output is correct
30 Correct 437 ms 45036 KB Output is correct
31 Correct 452 ms 45180 KB Output is correct
32 Correct 571 ms 53228 KB Output is correct