Submission #115246

#	Time	Username	Problem	Language	Result	Execution time	Memory
115246		IOrtroiii	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	1278 ms	186108 KiB

mousetrap

#include <bits/stdc++.h>

using namespace std;

const int N = 1000100;

int n, t, m;
vector<int> g[N];
vector<int> vals[N];
vector<int> tour;
bool on[N];
int pref[N];

bool dfs(int u, int p, int to) {
   tour.push_back(u);
   if (u == to) return true;
   for (int v : g[u]) {
      if (v != p) {
         if (dfs(v, u, to)) {
            return true;
         }
      }
   }
   tour.pop_back();
   return false;
}

int dfs2(int u, int p) {
   vector<int> vals;
   for (int v : g[u]) {
      if (v != p) {
         vals.push_back(dfs2(v, u));
      }
   }
   sort(vals.begin(), vals.end(), greater<int>());
   if (vals.empty()) return 0;
   else if (vals.size() == 1) return 1;
   else return vals.size() + vals[1];
}

bool solve(int md) {
   int free = 0;
   int use = 0;
   for (int i = tour.size() - 1; i > 0; --i) {
      ++free;
      int u = tour[i];
      int ptr = 0;
      while (ptr < vals[u].size() && free && use + pref[i] + vals[u][ptr] > md) {
         --free; ++ptr;
      }
      if (ptr < vals[u].size() && use + pref[i] + vals[u][ptr] > md) {
         return false;
      }
      use += ptr;
   }
   if (use > md) {
      return false;
   }
   return true;
}

int main() {
   scanf("%d %d %d", &n, &t, &m);
   for (int i = 1; i < n; ++i) {
      int u, v;
      scanf("%d %d", &u, &v);
      g[u].push_back(v);
      g[v].push_back(u);
   }
   dfs(t, -1, m);
   for (int u : tour) on[u] = true;
   for (int u : tour) {
      for (int v : g[u]) {
         if (!on[v]) {
            vals[u].push_back(dfs2(v, u));
         }
      }
      sort(vals[u].begin(), vals[u].end(), greater<int>());
   }
   for (int i = 1; i < tour.size(); ++i) {
      int u = tour[i];
      pref[i] = pref[i - 1];
      for (int v : g[u]) {
         if (!on[v]) pref[i]++;
      }
   }
   int l = 0, r = n - 1;
   while (l < r) {
      int md = (l + r) >> 1;
      if (solve(md)) r = md;
      else l = md + 1;
   }
   printf("%d\n", l);
}

Compilation message (stderr)

mousetrap.cpp: In function 'bool solve(int)':
mousetrap.cpp:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (ptr < vals[u].size() && free && use + pref[i] + vals[u][ptr] > md) {
              ~~~~^~~~~~~~~~~~~~~~
mousetrap.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (ptr < vals[u].size() && use + pref[i] + vals[u][ptr] > md) {
           ~~~~^~~~~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 1; i < tour.size(); ++i) {
                    ~~^~~~~~~~~~~~~
mousetrap.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &n, &t, &m);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:66:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &u, &v);
       ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35