Submission #616917

#	Time	Username	Problem	Language	Result	Execution time	Memory
616917		nghiass001	Mousetrap (CEOI17_mousetrap)	C++17	100 / 100	1114 ms	217292 KiB

mousetrap

#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i=(l); i<=(r); ++i)
#define REP(i, l, r) for(int i=(l); i<(r); ++i)
#define FORD(i, r, l) for(int i=(r); i>=(l); --i)
#define REPD(i, r, l)  for(int i=(r)-1; i>=(l); --i)
using namespace std;
const int N = 1e6 + 5;
int n, trap, mouse, cstep[N], deg[N], sdeg[N], p[N], avail[N];
vector<int> S[N], Q[N];
 
void Enter() {
    cin >> n >> trap >> mouse;
    REP(i, 1, n) {
        int u, v;
        cin >> u >> v;
        S[u].push_back(v);
        S[v].push_back(u);
    }
}
 
void DFS(int u, int pa) {
    if (u == mouse) avail[u] = 1;
    p[u] = pa;
    for(int v : S[u]) if (v != pa) {
        DFS(v, u);
        if (avail[v]) avail[u] = 1;
        else {
            Q[u].push_back(v);
            ++deg[u];
        }
    }
    sort(Q[u].begin(), Q[u].end(), [] (int x, int y) { return cstep[x] > cstep[y]; });
    if (deg[u] <= 1) cstep[u] = deg[u];
    if (deg[u] > 1) cstep[u] = cstep[Q[u][1]] + deg[u];
}
 
void DFS2(int u) {
    cstep[u] += sdeg[u];
    for(int v : S[u]) if (v != p[u]) {
        sdeg[v] = deg[u] + sdeg[u];
        DFS2(v);
    }
}
 
bool check(int x) {
    int sl = 0, timer = 0;
    for(int i = mouse; i != trap; i = p[i]) {
        ++timer;
        int c_now = 0;
        for(int v : Q[i]) if (cstep[v] + sl - c_now > x) ++sl, ++c_now;
        if (sl > timer || sl > x) return false;
    }
    return true;
}
 
void Process() {
    DFS(trap, 0);
    deg[trap] = 0;
    DFS2(trap);
    int l = 0, r = n, mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
}
 
int main()
{
    #define file "mousetrap"
    if (fopen(file".inp", "r")) {
        freopen(file".inp", "r", stdin);
        freopen(file".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    Enter();
    Process();
}

Compilation message (stderr)

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen(file".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(file".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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