Submission #170308

#	Time	Username	Problem	Language	Result	Execution time	Memory
170308		Ruxandra985	Mousetrap (CEOI17_mousetrap)	C++14	25 / 100	999 ms	79240 KiB

mousetrap

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define DIMN 1000010
using namespace std;
int fth[DIMN] , w[DIMN] , maxi[DIMN] , t , blocked[DIMN] , niv[DIMN];
int aib[DIMN];
pair <int,int> aint[4*DIMN];
vector <int> v[DIMN];
pair <int,int> s[DIMN];
inline void lazy_update (int nod,int st,int dr){
    if (!aint[nod].second) /// nu ii trb lazy
        return;
    if (st<dr){ /// nu e frunza
        aint[2*nod].second+=aint[nod].second; /// pass lazy
        aint[2*nod+1].second+=aint[nod].second;
    }
    aint[nod].first+=aint[nod].second;
    aint[nod].second=0;
}

int query (int nod , int st ,int dr , int poz){
    int mid = ( st + dr )/2 , x;
    lazy_update(nod , st , dr);
    if (st == dr)
        return aint[nod].first;

    if (poz<=mid)
        x = query (2*nod,st,mid,poz);
    else
        x = query (2*nod+1,mid+1,dr,poz);
    lazy_update (2*nod,st,mid);
    lazy_update (2*nod+1,mid+1,dr);
    return x;

}
void update_interv (int nod,int st,int dr,int l,int r,int add){
    int mid=(st+dr)/2;
    lazy_update (nod,st,dr);
    if (l<=st && dr<=r){
        aint[nod].second+=add; /// nu ma mai duc in jos
        lazy_update (nod,st,dr);
        return;
    }
    if (l<=mid)
        update_interv (2*nod,st,mid,l,r,add);
    if (mid+1<=r)
        update_interv (2*nod+1,mid+1,dr,l,r,add);
    lazy_update (2*nod,st,mid);
    lazy_update (2*nod+1,mid+1,dr);
}
void dfs (int nod,int tt){
    int i , vecin , maxii = 0 , poz;
    fth[nod] = tt;
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i];
        if (vecin != tt){
            niv[vecin] = 1 + niv[nod];
            dfs (vecin , nod);
            /// cat de in jos te poti duce din nod
        }
    }
   // if (nod == 5)
     //   printf ("a");
    /// maxi[nod] = nr de mutari ale soarecelui ca sa se plimbe in subarborele nod
    /// iar apoi sa revina in nod
    poz = -1;
    maxii = -1;
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i];
        if (vecin != tt){
            if (maxii < maxi[vecin]){
                maxii = maxi[vecin];
                poz = vecin;
            }
        }
    }
    maxi[nod] = -1;
    int x = v[nod].size();
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i];
        if (vecin != tt && vecin != poz){
            maxi[nod] = max (maxi[nod] , maxi[vecin] + 1 + 1 + x - 3);
            /// 1 ca sa cureti drumul vecin , nod dupa ce se blocheaza
            /// 1 ca sa blochezi cel mai nasol pasaj
        }
    }
    if (poz != -1){
        if (maxi[nod] == -1)
            maxi[nod] = maxi[poz] + 1 + x - 2;
        maxi[nod] = min(maxi[nod] , maxi[poz] + 1 + x - 2);
    }
    else maxi[nod] = 0;
    /// pot sa aleg sa nu blochez cel mai nasol pasaj
    if (v[nod].size() == 2){
        maxi[nod] = 1;
    }
}
int cmp (pair <int,int> a , pair <int,int> b){
    if (a.first != b.first)
        return a.first > b.first;
    return a.second < b.second;

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , i , x , y , nod , elem , mustblock , poz , sp ,sol , can , tt , el , p;
    int vecin , until;
    fscanf (fin,"%d%d%d",&n,&t,&m);
    for (i=1;i<n;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    //printf ("%d %d\n",v[t].size() , v[m].size());
    v[m].push_back(0);
    dfs (m , 0);
    /// practic soarecele isi alege un singur subarbore in care se duce cat vrea el
    /// apio cand se blocheaza
    nod = t;
    elem = 0;
    w[++elem] = t;
    while (fth[nod]){
        w[++elem] = fth[nod];
        nod = fth[nod];
    }
    mustblock = 0;
    for (i=1;i<=elem;i++){
        //printf ("%d %d\n",w[i],v[w[i]].size() - 2);
        if (w[i] == t)
            continue;
        mustblock += v[w[i]].size() - 2; /// nici tatal
    }
    /*for (i=0;i<v[150].size();i++){
        int vecin = v[150][i];
        if (vecin !=0)
        printf ("%d ",maxi[vecin]);
    }*/
    sol = 0;
    nod = m;
    can = 0;
    tt = 0;
    poz = elem;
    el = 0;
    /*while (nod != t){
        //printf ("%d ", nod);
        for (i=0;i<v[nod].size();i++){
            vecin = v[nod][i];
            if (vecin != tt && vecin != w[poz-1]){
                s[++el] = make_pair(make_pair(maxi[vecin] , niv[vecin]) , vecin);
                /// astia sunt vecinii pe care poti tu sa ii blochezi
            }
        }

        tt = nod;
        nod = w[poz-1];
        poz--;
    }*/
   // for (i=1;i<=el;i++)
     //   printf ("%d %d %d\n" , s[i].first.first , s[i].first.second , s[i].second);
   /* p = 1;
    can = niv[t];
    for (i=1;i<=niv[t];i++)
        update_interv (1 , 1 , n , i , i , i);
    /// o sa tin niv de la 1
    int nr = 0;
    while (can && p<=el){
        nod = s[p].second;
        p++;
        while (p<=el && !query(1 ,1 , n , niv[nod])){ /// poti
            nod = s[p].second;
            p++;
        }
        if (!query(1 ,1 , n , niv[nod]))
            break;
        update_interv (1 , 1 , n , niv[nod] , n , -1);
        blocked[nod] = 1;
        nr++;
        can--;
    }*/
    nod = m;
    tt = 0;
    int tos = 0;
    /// poti sa blochezi can pasaje in drumul
    can = 0;
    until = 0;
    while (nod != t){
        sp = 0;
        can++;
        tos = 0;
        if (v[nod].size() == 2){ /// efectiv nu ai ce sa faci


        }
        else {
            el = 0;
            for (i=0;i<v[nod].size();i++){
                vecin = v[nod][i];
                if (vecin != tt && vecin != w[elem-1]){
                    s[++el] = make_pair(maxi[vecin] , vecin);

                    tos++;
                    /// 1 ca sa cureti drumul vecin , nod dupa ce se blocheaza
                    /// 1 ca sa blochezi cel mai nasol pasaj
                }
            }
            sort (s + 1 , s + el + 1 , cmp);
            for (i=1;i<=el && can;i++){
                /// pe asta il blochezi la timp
                can--;
                until++;
                mustblock--;
            }
            if (!can && i<=el){
                sol = maxi[s[i].second] + 1 + mustblock - 1;
                fprintf (fout,"%d\n",sol + until);
                return 0;
            }
        }

        tt = nod;
        nod = w[elem-1];
        elem--;
    }
    //fprintf (fout,"%d",sol + nr);
    return 0;
}

Compilation message (stderr)

mousetrap.cpp: In function 'void dfs(int, int)':
mousetrap.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
mousetrap.cpp:70:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
mousetrap.cpp:81:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:200:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (i=0;i<v[nod].size();i++){
                      ~^~~~~~~~~~~~~~
mousetrap.cpp:110:54: warning: variable 'poz' set but not used [-Wunused-but-set-variable]
     int n , m , i , x , y , nod , elem , mustblock , poz , sp ,sol , can , tt , el , p;
                                                      ^~~
mousetrap.cpp:110:60: warning: variable 'sp' set but not used [-Wunused-but-set-variable]
     int n , m , i , x , y , nod , elem , mustblock , poz , sp ,sol , can , tt , el , p;
                                                            ^~
mousetrap.cpp:110:86: warning: unused variable 'p' [-Wunused-variable]
     int n , m , i , x , y , nod , elem , mustblock , poz , sp ,sol , can , tt , el , p;
                                                                                      ^
mousetrap.cpp:112:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d",&n,&t,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:114: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 / 20
• Subtask 2: 25 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35