Submission #170356

#	Time	Username	Problem	Language	Result	Execution time	Memory
170356		Ruxandra985	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	1114 ms	131244 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];
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
    }
    sol = 2000000000;
    nod = m;
    can = 0;
    tt = 0;
    poz = elem;
    el = 0;
    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
                if (!maxi[s[i].second])
                    break;
                if (i == el)
                    sol = min( sol ,  maxi[s[i].second] + mustblock);
                can--;
            }
            if (!can && i<=el){
                sol = min ( sol ,  maxi[s[i].second] + mustblock);
                fprintf (fout,"%d\n",sol);
                return 0;
            }
        }

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

Compilation message (stderr)

mousetrap.cpp: In function 'void dfs(int, int)':
mousetrap.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
mousetrap.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
mousetrap.cpp:40: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:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (i=0;i<v[nod].size();i++){
                      ~^~~~~~~~~~~~~~
mousetrap.cpp:69: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:69: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:69: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:70:17: warning: variable 'until' set but not used [-Wunused-but-set-variable]
     int vecin , until;
                 ^~~~~
mousetrap.cpp:71: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:73: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: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35