oj.uz

답안 #169531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
169531 2019-12-20T19:37:30 Z Ruxandra985 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 856 ms 59784 KB 
#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

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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10232 KB Output is correct
2 Correct 10 ms 10232 KB Output is correct
3 Correct 12 ms 10616 KB Output is correct
4 Correct 12 ms 10616 KB Output is correct
5 Correct 12 ms 10616 KB Output is correct
6 Correct 11 ms 10488 KB Output is correct
7 Correct 12 ms 10620 KB Output is correct
8 Correct 13 ms 10616 KB Output is correct
9 Correct 12 ms 10488 KB Output is correct
10 Correct 12 ms 10488 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10232 KB Output is correct
2 Correct 10 ms 10232 KB Output is correct
3 Correct 12 ms 10616 KB Output is correct
4 Correct 12 ms 10616 KB Output is correct
5 Correct 12 ms 10616 KB Output is correct
6 Correct 11 ms 10488 KB Output is correct
7 Correct 12 ms 10620 KB Output is correct
8 Correct 13 ms 10616 KB Output is correct
9 Correct 12 ms 10488 KB Output is correct
10 Correct 12 ms 10488 KB Output is correct
11 Correct 355 ms 42360 KB Output is correct
12 Correct 398 ms 44792 KB Output is correct
13 Correct 405 ms 48828 KB Output is correct
14 Correct 502 ms 53804 KB Output is correct
15 Correct 523 ms 55732 KB Output is correct
16 Correct 565 ms 52372 KB Output is correct
17 Correct 481 ms 54520 KB Output is correct
18 Correct 581 ms 52444 KB Output is correct
19 Correct 486 ms 56152 KB Output is correct
20 Correct 379 ms 48248 KB Output is correct
21 Correct 368 ms 46840 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10232 KB Output is correct
2 Correct 10 ms 10232 KB Output is correct
3 Correct 12 ms 10616 KB Output is correct
4 Correct 12 ms 10616 KB Output is correct
5 Correct 12 ms 10616 KB Output is correct
6 Correct 11 ms 10488 KB Output is correct
7 Correct 12 ms 10620 KB Output is correct
8 Correct 13 ms 10616 KB Output is correct
9 Correct 12 ms 10488 KB Output is correct
10 Correct 12 ms 10488 KB Output is correct
11 Correct 355 ms 42360 KB Output is correct
12 Correct 398 ms 44792 KB Output is correct
13 Correct 405 ms 48828 KB Output is correct
14 Correct 502 ms 53804 KB Output is correct
15 Correct 523 ms 55732 KB Output is correct
16 Correct 565 ms 52372 KB Output is correct
17 Correct 481 ms 54520 KB Output is correct
18 Correct 581 ms 52444 KB Output is correct
19 Correct 486 ms 56152 KB Output is correct
20 Correct 379 ms 48248 KB Output is correct
21 Correct 368 ms 46840 KB Output is correct
22 Correct 732 ms 55560 KB Output is correct
23 Correct 730 ms 53456 KB Output is correct
24 Correct 794 ms 53640 KB Output is correct
25 Correct 856 ms 59784 KB Output is correct
26 Correct 760 ms 55384 KB Output is correct
27 Correct 772 ms 53752 KB Output is correct
28 Correct 156 ms 14552 KB Output is correct
29 Correct 511 ms 48888 KB Output is correct
30 Correct 501 ms 48888 KB Output is correct
31 Correct 575 ms 49544 KB Output is correct
32 Correct 495 ms 46528 KB Output is correct