oj.uz

Submission #419003

# Submission time Handle Problem Language Result Execution time Memory
419003 2021-06-06T10:16:58 Z egekabas Mousetrap (CEOI17_mousetrap) C++14
20 / 100
 1751 ms 74328 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int n, t, m;
vector<int> g[1000009];
int trap[1000009];
int dp[1000009];
int edgecnt[1000009];

void dfs(int v, int prt){
    if(v == t){
        trap[v] = 1;
        return;
    }
    for(auto u : g[v])
        if(u != prt){
            dfs(u, v);
            if(trap[u])
                trap[v] = 1;
            else
                ++edgecnt[v];
        }
    dp[v] = edgecnt[v];
    for(auto u : g[v])
        if(u != prt && trap[u])
            dp[v] += dp[u];
}
int getans(int v, int prt, int curval){
    if(v == t) return 0;
    if(trap[v] == 0)
        curval -= edgecnt[v];
    if(curval < 0) return 1e9;
    vector<int> vec;
    for(auto u : g[v])
        if(u != prt && trap[u] == 0)
            vec.pb(getans(u, v, curval));
    int othneed = 0;
    for(auto u : g[v])
        if(u != prt && trap[u])
            othneed = getans(u, v, curval);
    sort(all(vec), greater<int>());
    int ret = 1e9;
    for(int i = 0; i < vec.size(); ++i)
        ret = min(ret, i+max(vec[i], othneed));
    ret = min(ret, (int)vec.size()+othneed);
    return max(ret-1, 0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n >> t >> m;
    for(int i = 0; i < n-1; ++i){
        int x, y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(m, 0);
    int l = 0, r = 1e9;
    while(l < r){
        int mid = (l+r)/2;
        if(getans(m, 0, mid-dp[m]) == 0)
            r = mid;
        else
            l = mid+1;
    }
    cout << l << '\n';
}

Compilation message

mousetrap.cpp: In function 'int getans(int, int, int)':
mousetrap.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = 0; i < vec.size(); ++i)
      |                    ~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 13 ms 23752 KB Output is correct
3 Correct 13 ms 23756 KB Output is correct
4 Correct 14 ms 23756 KB Output is correct
5 Correct 13 ms 23808 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 15 ms 23804 KB Output is correct
8 Correct 16 ms 23768 KB Output is correct
9 Correct 13 ms 23756 KB Output is correct
10 Correct 14 ms 23720 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1751 ms 74328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 13 ms 23752 KB Output is correct
3 Correct 13 ms 23756 KB Output is correct
4 Correct 14 ms 23756 KB Output is correct
5 Correct 13 ms 23808 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 15 ms 23804 KB Output is correct
8 Correct 16 ms 23768 KB Output is correct
9 Correct 13 ms 23756 KB Output is correct
10 Correct 14 ms 23720 KB Output is correct
11 Correct 13 ms 23756 KB Output is correct
12 Correct 15 ms 23868 KB Output is correct
13 Incorrect 15 ms 23756 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 13 ms 23752 KB Output is correct
3 Correct 13 ms 23756 KB Output is correct
4 Correct 14 ms 23756 KB Output is correct
5 Correct 13 ms 23808 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 15 ms 23804 KB Output is correct
8 Correct 16 ms 23768 KB Output is correct
9 Correct 13 ms 23756 KB Output is correct
10 Correct 14 ms 23720 KB Output is correct
11 Incorrect 1751 ms 74328 KB Output isn't correct
12 Halted 0 ms 0 KB -