oj.uz

Submission #172748

# Submission time Handle Problem Language Result Execution time Memory
172748 2020-01-02T14:12:59 Z nicolaalexandra One-Way Streets (CEOI17_oneway) C++14
100 / 100
 1072 ms 84716 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10232 KB Output is correct
2 Correct 11 ms 10232 KB Output is correct
3 Correct 14 ms 10744 KB Output is correct
4 Correct 15 ms 10872 KB Output is correct
5 Correct 14 ms 10872 KB Output is correct
6 Correct 13 ms 10616 KB Output is correct
7 Correct 15 ms 10872 KB Output is correct
8 Correct 20 ms 10872 KB Output is correct
9 Correct 14 ms 10616 KB Output is correct
10 Correct 14 ms 10616 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10232 KB Output is correct
2 Correct 11 ms 10232 KB Output is correct
3 Correct 14 ms 10744 KB Output is correct
4 Correct 15 ms 10872 KB Output is correct
5 Correct 14 ms 10872 KB Output is correct
6 Correct 13 ms 10616 KB Output is correct
7 Correct 15 ms 10872 KB Output is correct
8 Correct 20 ms 10872 KB Output is correct
9 Correct 14 ms 10616 KB Output is correct
10 Correct 14 ms 10616 KB Output is correct
11 Correct 598 ms 46760 KB Output is correct
12 Correct 566 ms 52212 KB Output is correct
13 Correct 616 ms 61356 KB Output is correct
14 Correct 700 ms 73844 KB Output is correct
15 Correct 714 ms 77172 KB Output is correct
16 Correct 954 ms 79480 KB Output is correct
17 Correct 717 ms 79920 KB Output is correct
18 Correct 860 ms 79612 KB Output is correct
19 Correct 719 ms 81564 KB Output is correct
20 Correct 624 ms 60404 KB Output is correct
21 Correct 503 ms 59000 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10232 KB Output is correct
2 Correct 11 ms 10232 KB Output is correct
3 Correct 14 ms 10744 KB Output is correct
4 Correct 15 ms 10872 KB Output is correct
5 Correct 14 ms 10872 KB Output is correct
6 Correct 13 ms 10616 KB Output is correct
7 Correct 15 ms 10872 KB Output is correct
8 Correct 20 ms 10872 KB Output is correct
9 Correct 14 ms 10616 KB Output is correct
10 Correct 14 ms 10616 KB Output is correct
11 Correct 598 ms 46760 KB Output is correct
12 Correct 566 ms 52212 KB Output is correct
13 Correct 616 ms 61356 KB Output is correct
14 Correct 700 ms 73844 KB Output is correct
15 Correct 714 ms 77172 KB Output is correct
16 Correct 954 ms 79480 KB Output is correct
17 Correct 717 ms 79920 KB Output is correct
18 Correct 860 ms 79612 KB Output is correct
19 Correct 719 ms 81564 KB Output is correct
20 Correct 624 ms 60404 KB Output is correct
21 Correct 503 ms 59000 KB Output is correct
22 Correct 931 ms 81080 KB Output is correct
23 Correct 981 ms 79552 KB Output is correct
24 Correct 1072 ms 80660 KB Output is correct
25 Correct 914 ms 84716 KB Output is correct
26 Correct 891 ms 81008 KB Output is correct
27 Correct 952 ms 79736 KB Output is correct
28 Correct 239 ms 14460 KB Output is correct
29 Correct 821 ms 61172 KB Output is correct
30 Correct 733 ms 61044 KB Output is correct
31 Correct 789 ms 61800 KB Output is correct
32 Correct 704 ms 61800 KB Output is correct