답안 #47084 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47084	2018-04-27T10:20:13 Z	qoo2p5	Mousetrap (CEOI17_mousetrap)	C++17	100 / 100	1190 ms	230704 KB

mousetrap

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 1e6;
const ll LINF = (ll) 1e18 + 1e9;
const ll MOD = (ll) 1e9 + 7;

#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (auto i = f; i < t; ++(i))
#define per(i, f, t) for (auto i = (f); i >= (t); --(i))

ll power(ll x, ll y, ll mod = MOD) {
    if (y == 0) {
        return 1;
    }
    if (y & 1) {
        return power(x, y - 1, mod) * x % mod;
    } else {
        ll tmp = power(x, y / 2, mod);
        return tmp * tmp % mod;
    }
}

template<typename A, typename B> bool mini(A &x, const B &y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

template<typename A, typename B> bool maxi(A &x, const B &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

void add(ll &x, ll y) {
    x += y;
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
}

void run();

#define TASK ""

int main() {
#ifdef LOCAL
    if (strlen(TASK) > 0) {
        cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
    }
#endif
#ifndef LOCAL
    if (strlen(TASK)) {
        freopen(TASK ".in", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    cout << fixed << setprecision(12);
    run();
    return 0;
}

// == SOLUTION == //

const int N = (int) 1e6 + 123;

int n, t, m;
vector<int> g[N];
int p[N];
int cost[N];
int up[N];

void calc(int v, int p = -1) {
    ::p[v] = p;
    int ptr = 0;
    int pos = -1;
    
    for (int u : g[v]) {
        if (u == p) {
            pos = ptr;
            continue;
        }
        
        up[u] = up[v];
        if (v != t) {
            up[u] += sz(g[v]) - 2;
        }
        calc(u, v);
        ptr++;
    }
    
    if (pos != -1) {
        g[v].erase(g[v].begin() + pos);
    }
    
    if (sz(g[v]) == 0) {
        cost[v] = 0;
    } else if (sz(g[v]) == 1) {
        cost[v] = 1;
    } else {
        vector<int> q;
        for (int u : g[v]) {
            q.push_back(cost[u]);
        }
        sort(all(q));
        cost[v] = sz(g[v]) + q[sz(q) - 2];
    }
}

void run() {
    cin >> n >> t >> m;
    rep(i, 0, n - 1) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    
    calc(t);
    vector<pair<int, int>> wow;
    int prv = -1;
    int w = m;
    int dist = 0;
    while (w != t) {
        for (int u : g[w]) {
            if (u == prv) {
                continue;
            }
            wow.pb({dist + 1, cost[u] + up[u] + (dist == 0)});
        }
        prv = w;
        w = p[w];
        dist++;
    }
    
    sort(all(wow));
    
    int left = -1;
    int right = n;
    while (right - left > 1) {
        int mid = (left + right) / 2;
        bool ok = 1;
        int cnt = 0;
        rep(i, 0, sz(wow)) {
            int j = i;
            while (j + 1 < sz(wow) && wow[j + 1].first == wow[j].first) {
                j++;
            }
            int ncnt = cnt;
            
            rep(k, i, j + 1) {
                auto it = wow[k];
                if (it.second + cnt <= mid) {
                    continue;
                }
                if (ncnt >= it.first) {
                    ok = 0;
                    break;
                }
                ncnt++;
            }
            
            cnt = ncnt;
            i = j;
        }
        
        ok &= (cnt <= mid);
        
        if (ok) {
            right = mid;
        } else {
            left = mid;
        }
    }
    
    cout << right << "\n";
}

Compilation message

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

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	23800 KB	Output is correct
2	Correct	20 ms	23912 KB	Output is correct
3	Correct	20 ms	23912 KB	Output is correct
4	Correct	21 ms	24012 KB	Output is correct
5	Correct	21 ms	24012 KB	Output is correct
6	Correct	26 ms	24012 KB	Output is correct
7	Correct	21 ms	24056 KB	Output is correct
8	Correct	21 ms	24056 KB	Output is correct
9	Correct	21 ms	24056 KB	Output is correct
10	Correct	21 ms	24096 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	519 ms	67156 KB	Output is correct
2	Correct	548 ms	67156 KB	Output is correct
3	Correct	1157 ms	68220 KB	Output is correct
4	Correct	529 ms	68220 KB	Output is correct
5	Correct	1123 ms	68368 KB	Output is correct
6	Correct	1148 ms	68368 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	23800 KB	Output is correct
2	Correct	20 ms	23912 KB	Output is correct
3	Correct	20 ms	23912 KB	Output is correct
4	Correct	21 ms	24012 KB	Output is correct
5	Correct	21 ms	24012 KB	Output is correct
6	Correct	26 ms	24012 KB	Output is correct
7	Correct	21 ms	24056 KB	Output is correct
8	Correct	21 ms	24056 KB	Output is correct
9	Correct	21 ms	24056 KB	Output is correct
10	Correct	21 ms	24096 KB	Output is correct
11	Correct	20 ms	68368 KB	Output is correct
12	Correct	21 ms	68368 KB	Output is correct
13	Correct	21 ms	68368 KB	Output is correct
14	Correct	21 ms	68368 KB	Output is correct
15	Correct	21 ms	68368 KB	Output is correct
16	Correct	21 ms	68368 KB	Output is correct
17	Correct	21 ms	68368 KB	Output is correct
18	Correct	21 ms	68368 KB	Output is correct
19	Correct	22 ms	68368 KB	Output is correct
20	Correct	21 ms	68368 KB	Output is correct
21	Correct	21 ms	68368 KB	Output is correct
22	Correct	20 ms	68368 KB	Output is correct

Subtask #4
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	23800 KB	Output is correct
2	Correct	20 ms	23912 KB	Output is correct
3	Correct	20 ms	23912 KB	Output is correct
4	Correct	21 ms	24012 KB	Output is correct
5	Correct	21 ms	24012 KB	Output is correct
6	Correct	26 ms	24012 KB	Output is correct
7	Correct	21 ms	24056 KB	Output is correct
8	Correct	21 ms	24056 KB	Output is correct
9	Correct	21 ms	24056 KB	Output is correct
10	Correct	21 ms	24096 KB	Output is correct
11	Correct	519 ms	67156 KB	Output is correct
12	Correct	548 ms	67156 KB	Output is correct
13	Correct	1157 ms	68220 KB	Output is correct
14	Correct	529 ms	68220 KB	Output is correct
15	Correct	1123 ms	68368 KB	Output is correct
16	Correct	1148 ms	68368 KB	Output is correct
17	Correct	20 ms	68368 KB	Output is correct
18	Correct	21 ms	68368 KB	Output is correct
19	Correct	21 ms	68368 KB	Output is correct
20	Correct	21 ms	68368 KB	Output is correct
21	Correct	21 ms	68368 KB	Output is correct
22	Correct	21 ms	68368 KB	Output is correct
23	Correct	21 ms	68368 KB	Output is correct
24	Correct	21 ms	68368 KB	Output is correct
25	Correct	22 ms	68368 KB	Output is correct
26	Correct	21 ms	68368 KB	Output is correct
27	Correct	21 ms	68368 KB	Output is correct
28	Correct	20 ms	68368 KB	Output is correct
29	Correct	21 ms	68368 KB	Output is correct
30	Correct	515 ms	80880 KB	Output is correct
31	Correct	516 ms	94364 KB	Output is correct
32	Correct	519 ms	217220 KB	Output is correct
33	Correct	507 ms	230704 KB	Output is correct
34	Correct	1158 ms	230704 KB	Output is correct
35	Correct	1185 ms	230704 KB	Output is correct
36	Correct	1190 ms	230704 KB	Output is correct
37	Correct	1172 ms	230704 KB	Output is correct
38	Correct	1016 ms	230704 KB	Output is correct
39	Correct	1006 ms	230704 KB	Output is correct
40	Correct	1031 ms	230704 KB	Output is correct

답안 #47084

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 25.0 / 25.0

Subtask #3 20.0 / 20.0

Subtask #4 35.0 / 35.0

Subtask #1
20.0 / 20.0

Subtask #2
25.0 / 25.0

Subtask #3
20.0 / 20.0

Subtask #4
35.0 / 35.0