| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 170355 | 2019-12-24T20:49:25 Z | Ruxandra985 | Mousetrap (CEOI17_mousetrap) | C++14 | 980 ms | 68216 KB |
#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] + 1 + mustblock - 1 + until);
can--;
until++;
mustblock--;
}
if (!can && i<=el){
sol = min ( sol , maxi[s[i].second] + 1 + mustblock - 1 + until);
fprintf (fout,"%d\n",sol);
return 0;
}
}
tt = nod;
nod = w[elem-1];
elem--;
}
sol = min (sol , until);
fprintf (fout,"%d",until);
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 24 ms | 23832 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 435 ms | 66908 KB | Output is correct |
| 2 | Correct | 393 ms | 62840 KB | Output is correct |
| 3 | Correct | 980 ms | 68160 KB | Output is correct |
| 4 | Correct | 433 ms | 45992 KB | Output is correct |
| 5 | Correct | 974 ms | 68216 KB | Output is correct |
| 6 | Correct | 940 ms | 68124 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 24 ms | 23832 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 24 ms | 23832 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |