Submission #711189

#	Time	Username	Problem	Language	Result	Execution time	Memory
711189		groshi	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	212 KiB

oneway

#include<bits/stdc++.h>

using namespace std;
struct wi{
    vector<int> Q,Q2;
    int skoki[20];
    int pocz=0,kon=0;
    int most=0;
    int low=0;
    bool odw=0;
    int pree=0;
    int poz=0;
    int nr_do_ojca;
}*w;
int t[200000][2];
int wypisz[200000];
bool essa[200000];
int pre=1;
void dodaj(int x)
{
    int gdzie=0;
    while(w[w[x].skoki[gdzie]].skoki[gdzie]!=0)
    {
        w[x].skoki[gdzie+1]=w[w[x].skoki[gdzie]].skoki[gdzie];
        gdzie++;
    }
}
void reku(int x,int ojc)
{
    w[x].poz=w[ojc].poz+1;
    w[x].skoki[0]=ojc;
    dodaj(x);
    w[x].odw=1;
    w[x].pree=pre;
    w[x].low=pre;
    pre++;
    for(int i=0;i<w[x].Q.size();i+=2)
    {
        int pom=w[x].Q[i];
        if(pom==ojc)
            continue;
        if(w[pom].odw)
            w[x].low=min(w[x].low,w[pom].pree);
        else{
            w[pom].Q2.push_back(x);
            w[x].Q2.push_back(pom);
            w[pom].Q2.push_back(w[x].Q[i+1]);
            w[x].Q2.push_back(w[x].Q[i+1]);
            w[pom].nr_do_ojca=w[x].Q[i+1];
            reku(pom,x);
            w[x].low=min(w[x].low,w[pom].low);
            if(w[pom].low>w[x].pree)
                w[pom].most=1;
        }
    }
}
int lcaa(int x,int y)
{
    if(w[x].poz>w[y].poz)
        swap(x,y);
    for(int i=19;i>=0;i--)
        if(w[w[y].skoki[i]].poz>=w[x].poz)
            y=w[y].skoki[i];
    if(x==y)
        return x;
    for(int i=19;i>=0;i--)
        if(w[x].skoki[i]!=w[y].skoki[i])
        {
            x=w[x].skoki[i];
            y=w[y].skoki[i];
        }
    return w[x].skoki[0];
}
void reku2(int x,int ojc)
{
    for(int i=0;i<w[x].Q2.size();i+=2)
    {
        int pom=w[x].Q2[i];
        if(pom==ojc)
            continue;
        reku2(pom,x);
        w[x].pocz+=w[pom].pocz;
        w[x].kon+=w[x].kon;
    }
    if(w[x].pocz==0 && w[x].kon==0)
        return;
    if(w[x].most==0)
        return;
    if(w[x].pocz!=0 && w[x].kon!=0)
    {
        int mam=w[x].nr_do_ojca;
        essa[mam]=1;
        return;
    }
    if(w[x].pocz==0 && w[x].kon!=0)
    {
        int mam=w[x].nr_do_ojca;
        if(t[mam][0]==x)
        {
            if(wypisz[mam]==2)
                essa[mam]=1;
            else wypisz[mam]=1;
        }
        else {
            if(wypisz[mam]==1)
                essa[mam]=1;
            else wypisz[mam]=2;
        }
    }
    else{
        int mam=w[x].nr_do_ojca;
        if(t[mam][0]==x)
        {
            if(wypisz[mam]==1)
                essa[mam]=1;
            else wypisz[mam]=2;
        }
        else {
            if(wypisz[mam]==2)
                essa[mam]=1;
            else wypisz[mam]=1;
        }
    }
}
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m,x,y;
    cin>>n>>m;
    w=new wi[n+3];
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        w[x].Q.push_back(y);
        w[y].Q.push_back(x);
        w[x].Q.push_back(i);
        w[y].Q.push_back(i);
        t[i][0]=x;
        t[i][1]=y;
    }
    reku(1,0);
    int zap;
    cin>>zap;
    while(zap--)
    {
        cin>>x>>y;
        w[x].pocz++;
        w[y].kon++;
        //cout<<x<<" "<<y<<": "<<lcaa(x,y)<<"\n";
        int lca=lcaa(x,y);
        w[lca].pocz--;
        w[lca].kon--;
    }
    reku2(1,0);
    for(int i=1;i<=m;i++)
    {
        if(wypisz[i]==0 || essa[i]==1)
            cout<<"B";
        else if(wypisz[i]==1)
            cout<<"L";
        else if(wypisz[i]==2)
            cout<<"R";
    }
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void reku(int, int)':
oneway.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0;i<w[x].Q.size();i+=2)
      |                 ~^~~~~~~~~~~~~~
oneway.cpp: In function 'void reku2(int, int)':
oneway.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0;i<w[x].Q2.size();i+=2)
      |                 ~^~~~~~~~~~~~~~~

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