Submission #169531

#	Time	Username	Problem	Language	Result	Execution time	Memory
169531		Ruxandra985	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	856 ms	59784 KiB

oneway

#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int low[DIMN],lvl[DIMN] , f[DIMN] , d[DIMN] , l[DIMN] , up[DIMN] , fth[20][DIMN];
int lg[DIMN] , poz[DIMN];
int lnt = 0;
map <pair <int,int> , int> mc , nr_mch;
pair <int,int> muchie[DIMN];
stack <int > st;
vector <int> v[DIMN] , w[DIMN] , dfs_tree[DIMN] , aint[DIMN];
int x;
void precalc (int nod){
    int i,vecin;
    d[nod]=1;
    f[nod]=1;
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (!f[vecin]){
            lvl[vecin]=1+lvl[nod];
            dfs_tree[nod].push_back(vecin);
            precalc (vecin);
            d[nod]+=d[vecin];

        }
    }
}

void dfs_lant(int nod,int tata){
    int i,vecin,ok=0,maxi,fiu;
    fth[0][nod] = tata;
    f[nod] = 1;
    maxi=0;
    fiu=0;
    for (i=0;i<dfs_tree[nod].size();i++){
        vecin=dfs_tree[nod][i];
        if (vecin != tata){
            ok=1;
            dfs_lant(vecin,nod);
            if (d[vecin]>maxi){
                maxi=d[vecin];
                fiu=vecin;
            }
        }
    }
    if (!ok){ /// frunza
        lnt++;
        l[nod]=lnt; /// lantul din care apartine
        w[lnt].push_back(nod);
    }else { /// unim cu poz
        w[l[fiu]].push_back(nod);
        l[nod]=l[fiu];
        for (i=0;i<dfs_tree[nod].size();i++){
            vecin=dfs_tree[nod][i];
            if (vecin!=tata && vecin!=fiu)
                up[l[vecin]]=nod; /// din lantul vecinului trecem in lantul nodului
        }
    }
}

void dfs_biconexe (int nod,int tt){
    int i,vecin , nr = 0;
    low[nod]=lvl[nod];
    st.push(nod);
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (vecin==tt)
            continue;
        if (lvl[vecin]==0){
            lvl[vecin]=1+lvl[nod];
            dfs_biconexe(vecin,nod);
            low[nod]=min(low[nod],low[vecin]);
            if (low[vecin]>=lvl[nod]){ /// nod e un nod critic
                //mc[make_pair(nod,vecin)] = 1;

                nr = 1;
                do{
                    x=st.top();
                    st.pop();
                    nr++;
                }
                while (x!=vecin);

                if (nr == 2){
                    mc[make_pair(nod,vecin)] = 1;
                    //printf ("%d %d\n" , nod, vecin);
                }

                /// am scos din stiva muchiile care sunt in subarborele nod->vecin
            }
        }
        else low[nod]=min(low[nod],lvl[vecin]);
    }
}

pair <int,int> lca (int n , int x , int y){
    int dif , p2 , swapped = 0;
    /// aducem pe ac nivel
    if (lvl[x] < lvl[y]){
        swapped = 1;
        swap(x , y); /// x e mai jos
    }
    dif = lvl[x] - lvl[y] - 1;
    /// stramosul dif al lui x

     while (dif > 0 && x!=0){
        x=fth[lg[dif]][x];
        dif=dif-(1<<lg[dif]);
    }
    /// acum sunt pe acelasi nivel
    if (fth[0][x] == y){ /// y era tatal lui x
        if (!swapped)
            return make_pair(x , -1);
        else return make_pair(-1 , x);
    }
    if (dif != -1)
        x = fth[0][x];

    for (p2 = lg[n] ; p2>=0 ; p2--){
        if (fth[p2][x] != fth[p2][y]){
            x = fth[p2][x];
            y = fth[p2][y];
        }
    }
    if (!swapped)
        return make_pair(x , y);
    else return make_pair(y , x);
}

void update_aint (int lant , int nod , int st , int dr , int l , int r , int val){
    int mid = (st + dr)/2;
    //if (lant == 23322){
      //  printf ("%d %d %d\n" , l , r , val);
    //}
    if (l <= st && dr <= r){
        aint[lant][nod] = val; /// tot intervalul ala are aceeasi valoare (1 sau -1)
        return;
    }

    if (l <= mid)
        update_aint (lant , 2*nod , st , mid , l , r, val);

    if (mid+1 <= r)
        update_aint (lant , 2*nod+1 , mid+1 , dr , l , r, val);

}

void update (int x , int y , int val){
    if (l[x]!=l[y]){ /// avansam
        if (lvl[up[l[x]]]>lvl[up[l[y]]]){
            update(up[l[x]] , y , val);
            update_aint( l[x] , 1 , 0 , w[l[x]].size()-1 , 0 , poz[x] , val);
        }
        else {
            update (x,up[l[y]] , val);
            update_aint(l[y],1,0,w[l[y]].size()-1,0,poz[y] , val);
        }
    }
    else {
        return update_aint(l[x],1,0,w[l[x]].size()-1,min(poz[y] , poz[x]),max(poz[y] , poz[x]) , val);
    }

}

int query_aint (int lant,int nod,int st,int dr,int px){
    int mid;
    if (aint[lant][nod] !=0 || st == dr)
        return aint[lant][nod];
    mid=(st+dr)/2;
    if (px<=mid)
        return query_aint(lant,2*nod,st,mid,px);
    else
        return query_aint(lant,2*nod+1,mid+1,dr,px);
}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n, m , i , x , y , p , vecin , nod , sol;
    pair <int,int> z;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
        nr_mch[make_pair(x , y)]++;
        nr_mch[make_pair(y , x)]++;
        muchie[i] = make_pair(x , y);
    }
    for (i=1;i<=n;i++){
        if (!lvl[i]){
            lvl[i] = 1;
            dfs_biconexe ( i, 0 );
        }
    }
    /// vreau sa gasesc noduri critice
    /// daca un drum intre X Y trece printr o mch critica ins ca
    /// toate drumurile intre X Y trec pin acea muchie =>
    /// muchia aia are sens prestabilit

    for (i=1;i<=n;i++){
        if (!f[i])
            precalc(i);
    }

    memset (f , 0 , sizeof ( f ));

    for (i=1;i<=n;i++){
        if (!f[i])
            dfs_lant(i , 0);
    }

    /// fiecare nod al catelea e
    for (i=1;i<=lnt;i++){
        reverse(w[i].begin(),w[i].end());
        p=0;
        for (vector <int> :: iterator j=w[i].begin();j!=w[i].end();j++){
            /// pozitia lui din lantul curent
            vecin=*j;
            poz[vecin]=p;
            p++;
        }
    }
    /// folosesti aint

    for (i=1;i<=lnt;i++)
        aint[i].resize(w[i].size()*5);

    /// ai precalculat pentru heavy

    for (i=2;i<=n;i++){
        lg[i]=lg[i/2]+1;
    }
    int k = 1;
    while ((1<<k)<=n){
        for (i=1;i<=n;i++){
            fth[k][i] = fth[k-1][fth[k-1][i]] ;
        }
        k++;
    }

    /// ai precalculat pe lca in log pt ca ti a fost lene sa faci cu query in o(1)

    fscanf (fin,"%d",&p);
    for (i=1;i<=p;i++){
        fscanf (fin,"%d%d",&x,&y);
        if (x == y)
            continue;
        //if (x == 63466 || y == 63466)
          //  printf ("b");
        z = lca ( n , x, y );
        /// update pe lant x , z cu 1 = RIGHT
        /// update pe lant y , z cu -1 = LEFT
        if (-1 != z.first)
            update (x , z.first , 1);
        if (-1 != z.second)
            update (y , z.second, -1);
    }

    /// am facut updateurile , e momentul sa fac queryurile

    for (i=1;i<=m;i++){
        //if (i == 45350)
          //  printf ("a");
        if ( ( mc[muchie[i]] || mc[make_pair(muchie[i].second , muchie[i].first)] ) &&
            nr_mch[muchie[i]] == 1 && muchie[i].first != muchie[i].second){
            /// e muchie critica , trebuie sa vedem ce valoare are
            if (mc[muchie[i]])
                nod = muchie[i].second;
            else nod = muchie[i].first;

            sol = query_aint (l[nod] , 1 , 0 , w[l[nod]].size() - 1 , poz[nod]);

            if (sol == 0)
                fprintf (fout,"B");
            else if (sol == -1){
                if (nod == muchie[i].first)
                    fprintf (fout,"L");
                else fprintf (fout,"R");
            }
            else {
                if (nod == muchie[i].first)
                    fprintf (fout,"R");
                else fprintf (fout,"L");
            }

        }
        else fprintf (fout,"B");
    }

    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void precalc(int)':
oneway.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs_lant(int, int)':
oneway.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<dfs_tree[nod].size();i++){
              ~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<dfs_tree[nod].size();i++){
                  ~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs_biconexe(int, int)':
oneway.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:181:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
oneway.cpp:183:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
oneway.cpp:244:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d",&p);
     ~~~~~~~^~~~~~~~~~~~~
oneway.cpp:246:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

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