Submission #169522

#	Time	Username	Problem	Language	Result	Execution time	Memory
169522		Ruxandra985	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	12 ms	10488 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];
int 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;
    f[nod] = 1;
    //if (nod == 54)
      //  printf ("a");
    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]);
    }
}


void update_aint (int lant , int nod , int st , int dr , int l , int r , int val){
    int mid = (st + dr)/2;
    //if ( l == 0 && r == 0 )
      //  printf ("%d %d\n",st,dr);
    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){
   // printf ("%d %d\n" , x , y );
    if (l[x]!=l[y]){ /// avansam
        if (lvl[up[l[x]]]>lvl[up[l[y]]]){
            update(up[l[x]] , y);
            update_aint( l[x] , 1 , 0 , w[l[x]].size()-1 , 0 , poz[x] , 1);
        }
        else {
            update ( x , up[l[y]]);
            update_aint(l[y],1,0,w[l[y]].size()-1,0,poz[y] , -1);
        }
    }
    else {
        if (lvl[x] < lvl[y]) /// x e lca ul , te duci in jos , pui -1
            update_aint(l[x],1,0,w[l[x]].size()-1,min(poz[y] , poz[x]),max(poz[y] , poz[x]) , -1);
        else
            update_aint(l[x],1,0,w[l[x]].size()-1,min(poz[y] , poz[x]),max(poz[y] , poz[x]) , 1);
    }

}

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

    /// nu imi mai trb lca ul

    fscanf (fin,"%d",&p);
    for (i=1;i<=p;i++){
        fscanf (fin,"%d%d",&x,&y);
        /// update pe lant x , z cu 1 = RIGHT
        /// update pe lant y , z cu -1 = LEFT
        update (x , y);
    }

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

    for (i=1;i<=m;i++){
        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:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<dfs_tree[nod].size();i++){
              ~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:53: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:65: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:152: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:154: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:204: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:206: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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40