Submission #170199

#	Time	Username	Problem	Language	Result	Execution time	Memory
170199		Ruxandra985	Mousetrap (CEOI17_mousetrap)	C++14	0 / 100	967 ms	77668 KiB

mousetrap

#include <cstdio>
#include <vector>
#include <iostream>
#define DIMN 1000010
using namespace std;
int sol;
int fth[DIMN] , w[DIMN] , maxi[DIMN] , t;
vector <int> v[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){
            dfs (vecin , nod);
            /// cat de in jos te poti duce din nod
        }
    }
    /// maxi[nod] = nr de mutari ale soarecelui ca sa se plimbe in subarborele nod
    /// iar apoi sa revina in nod
    poz = -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;
            }
        }
    }
    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)
        maxi[nod] = min(maxi[nod] , maxi[poz] + 1 + x - 2);
    /// pot sa aleg sa nu blochez cel mai nasol pasaj
}
void dfs2 (int nod,int tt,int elem , int mustblock){
    int i ,vecin , maxii = 0 , poz , sp;

    if (nod == t)
        return;

    poz = -1;
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i];
        if (vecin != tt && vecin != w[elem]){
            if (maxii < maxi[vecin]){
                maxii = maxi[vecin];
                poz = vecin;
            }
        }
    }
    sp = 0;
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i];
        if (vecin != tt && vecin != poz && vecin != w[elem]){
            sp = max (sp , maxi[vecin] + 1 + 1 + mustblock - 1 - 1);
            /// 1 ca sa cureti drumul vecin , nod dupa ce se blocheaza
            /// 1 ca sa blochezi cel mai nasol pasaj
        }
    }
    if (poz != -1)
        sol = max(sol , min(sp , maxi[poz] + 1 + mustblock - 1) );

    dfs2 (w[elem] , nod , elem-1 , mustblock - v[nod].size() + 2);
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , i , x , y , nod , elem , mustblock;
    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);
    }
    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++){
        if (w[i] == t)
            continue;
        mustblock += v[w[i]].size() - 2; /// nici tatal
    }
    sol = 0;
    dfs2 (m , 0 , elem , mustblock);
    fprintf (fout,"%d",sol);
    return 0;
}

Compilation message (stderr)

mousetrap.cpp: In function 'void dfs(int, int)':
mousetrap.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
mousetrap.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
mousetrap.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
mousetrap.cpp: In function 'void dfs2(int, int, int, int)':
mousetrap.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
mousetrap.cpp:61: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:79: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:81: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: 0 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35