Submission #172748

#	Time	Username	Problem	Language	Result	Execution time	Memory
172748		nicolaalexandra	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	1072 ms	84716 KiB

oneway

#include <bits/stdc++.h>
#define DIM 100010
using namespace std;

int whatChain[DIM],positionInChain[DIM],chainFatherNode[DIM],level[DIM],Size[DIM];
int viz[DIM],low[DIM],niv[DIM],b[DIM],E[DIM*3],first[DIM];
pair <int,int> rmq[20][DIM*3],mch[DIM];
vector <int> chains[DIM],L[DIM],edg[DIM],aint[DIM];
map < pair<int,int>, int > mch_critica,cnt;
deque <int> s;
int n,m,p,i,j,x,y,k,lca;
int nr_chains;
void dfs (int nod, int tata){
    viz[nod] = 1;
    low[nod] = niv[nod] = 1+niv[tata];
    s.push_back (nod);
    for (auto vecin:edg[nod]){
        if (vecin == tata)
            continue;
        if (viz[vecin])
            low[nod] = min (low[nod],niv[vecin]);
        else {
            dfs (vecin,nod);
            low[nod] = min (low[nod],low[vecin]);
            if (low[vecin] >= niv[nod]){
                int x, cnt = 1;
                do{
                    cnt++;
                    x = s.back();
                    s.pop_back();
                } while (x != vecin);
                if (cnt == 2){
                    /// am muchie critica
                    //cout<<nod<<" "<<vecin<<endl;
                    mch_critica[make_pair(nod,vecin)] = 1;
                }}}}}
void build_tree (int nod, int tata){
    viz[nod] = 1;
    for (auto vecin:edg[nod]){
        if (!viz[vecin]){
            L[nod].push_back(vecin);
            L[vecin].push_back(nod);
            build_tree (vecin,nod);
        }}}
void pre_dfs (int nod, int tata){
    E[++k] = nod; /// parc. euler
    first[nod] = k;
    Size[nod] = 1;
    level[nod] = 1 + level[tata];
    int ok = 0;
    for (auto vecin:L[nod]){
        if (vecin == tata)
            continue;
        ok = 1;
        pre_dfs (vecin,nod);
        Size[nod] += Size[vecin];
        E[++k] = nod;
    }
    if (!ok){ /// e frunza
        nr_chains++;
        chains[nr_chains].push_back(0);
        chains[nr_chains].push_back(nod);
        positionInChain[nod] = 1;
        whatChain[nod] = nr_chains;
    } else {
        int maxim = 0, poz = 0;
        for (auto vecin:L[nod]){
            if (vecin == tata)
                continue;
            if (Size[vecin] > maxim){
                maxim = Size[vecin];
                poz = vecin;
            }
        }
        chains[whatChain[poz]].push_back(nod);
        positionInChain[nod] = chains[whatChain[poz]].size()-1;
        whatChain[nod] = whatChain[poz];
        /// chain father node
        for (auto vecin:L[nod]){
            if (vecin == tata || vecin == poz)
                continue;
            chainFatherNode[whatChain[vecin]] = nod;
        }}}
int get_lca (int x, int y){
    int pozx = first[x], pozy = first[y];
    if (pozx > pozy)
        swap (pozx,pozy);
    int nr = b[pozy-pozx+1];
    pair <int,int> sol = min (rmq[nr][pozx],rmq[nr][pozy-(1<<nr)+1]);
    return E[sol.second];
}

int query_aint (int chain, int nod, int st, int dr, int poz){
    if (st == dr || aint[chain][nod])
        return aint[chain][nod];

    int mid = (st+dr)>>1;
    if (poz <= mid)
        query_aint (chain,nod<<1,st,mid,poz);
    else query_aint (chain,(nod<<1)|1,mid+1,dr,poz);
}

void update_aint (int chain, int nod, int st, int dr, int x, int y, int val){
    if (x <= st && dr <= y){
        aint[chain][nod] = val;
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        update_aint (chain,nod<<1,st,mid,x,y,val);
    if (y > mid)
        update_aint (chain,(nod<<1)|1,mid+1,dr,x,y,val);
}

void update_heavy (int x, int y, int val){
    if (whatChain[x] == whatChain[y]){
        int posx = positionInChain[x], posy = positionInChain[y];
        if (posx > posy)
            swap (posx,posy);
        if (x == lca)
            posx++;
        if (y == lca)
            posy--;
        if (posx > posy)
            return;
        update_aint (whatChain[x],1,1,chains[whatChain[x]].size()-1,posx,posy,val);
        return;
    }

    if (level[chainFatherNode[whatChain[x]]] <= level[chainFatherNode[whatChain[y]]])
        swap (x,y);


    int poz_st = positionInChain[x], poz_dr = chains[whatChain[x]].size()-1;
    if (chains[whatChain[x]][poz_st] == lca)
        poz_st++;
    if (chains[whatChain[x]][poz_dr] == lca)
        poz_dr--;
    if (poz_st <= poz_dr)
        update_aint (whatChain[x],1,1,chains[whatChain[x]].size()-1,poz_st,poz_dr,val);
    int nr = chainFatherNode[whatChain[x]];
    update_heavy (nr,y,val);
}
int main (){
    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=m;i++){
        cin>>x>>y;
        edg[x].push_back(y);
        edg[y].push_back(x);
        mch[i] = make_pair (x,y);
        cnt[make_pair(x,y)]++, cnt[make_pair(y,x)]++;
    }
    /// trb sa gasesc muchiile critice, restul sigur fac parte dintr-un ciclu
    /// deci sunt bidirectionale
    for (i=1;i<=n;i++){
        if (!viz[i]){
            s.clear();
            dfs (i,0);
        }}

    /// construiesc arborele
    memset (viz,0,sizeof viz);
    for (i=1;i<=n;i++){
        if (!viz[i])
            build_tree (i,0);
    }
    /// precalculare pt lca si heavy <3
    for (i=1;i<=n;i++)
        if (!level[i])
            pre_dfs (i,0);

    /// lca
    for (int i=1;i<=k;i++)
        rmq[0][i] = make_pair(level[E[i]],i);
    for (i=1;(1<<i)<=k;i++)
        for (j=1;j<=k;j++){
            rmq[i][j] = rmq[i-1][j];
            if (j+(1<<(i-1)) <= k && rmq[i-1][j+(1<<(i-1))].first < rmq[i][j].first)
                rmq[i][j] = rmq[i-1][j+(1<<(i-1))];
        }
    for (i=2;i<=k;i++)
        b[i] = b[i/2] + 1;

    for (i=1;i<=nr_chains;i++){
        for (j=0;j<=4*chains[i].size();j++)
            aint[i].push_back(0);
    }

    //for (i=1;i<=n;i++)
        //fout<<positionInChain[i]<<" ";

    cin>>p;
    for (i=1;i<=p;i++){
        cin>>x>>y;
        lca = get_lca (x,y);
        /// trb sa am grija sa nu dau update in lca
        if (x != lca)
            update_heavy (x,lca,1); /// 1 pt stanga - ma duc in sus
        if (y != lca)
            update_heavy (y,lca,2); /// 2 pt dreapta - ma duc in jos

    }
    for (i=1;i<=m;i++){
        int x = mch[i].first, y = mch[i].second;
        if ((mch_critica[make_pair(x,y)] || mch_critica[make_pair(y,x)]) && x != y && cnt[mch[i]] == 1){
            int ok = 0;
            if (level[x] < level[y]){
                swap (x,y);
                ok = 1;
            }

            int sol = query_aint (whatChain[x],1,1,chains[whatChain[x]].size()-1,positionInChain[x]);

            if (sol == 0){
                cout<<"B";
            } else {
                if (sol == 1){
                    if (!ok)
                        cout<<"R";
                    else cout<<"L";
                } else {
                    if (!ok)
                        cout<<"L";
                    else cout<<"R";
                }}
        } else cout<<"B";
    }



    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:188:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=0;j<=4*chains[i].size();j++)
                  ~^~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int query_aint(int, int, int, int, int)':
oneway.cpp:101:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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