oj.uz

Submission #468560

# Submission time Handle Problem Language Result Execution time Memory
468560 2021-08-28T17:29:40 Z ACmachine Mousetrap (CEOI17_mousetrap) C++17
100 / 100
 1695 ms 207928 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
typedef vector<int> vi;
typedef vector<ll> vll;
 
#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
	
const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};
 
void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;
 
template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "[";  REP(i, U) out << v[i] << ", ";  out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
 
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
  
int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
    int n, t, m;
    cin >> n >> t >> m;
    t--; m--;
    vector<vector<int>> g(n);
    REP(i, n - 1){
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    vector<int> dp(n, INF);
    vector<int> par(n, -1);
    function<void(int, int)> tmd = [&](int v, int p){
        par[v] = p;
        for(int x : g[v]){
            if(x == p) continue;
            tmd(x, v);
        }
    };
    tmd(t, -1);
    vector<int> path;
    vector<bool> onpath(n, false);
    int vv = m;
    while(vv != -1){
        path.pb(vv);
        onpath[vv] = true;
        vv = par[vv];
    }
    function<void(int, int, int)> dfs = [&](int v, int p, int d){
        if(onpath[v])
            d = 0;
        par[v] = p;
        vector<int> vect;
        for(int x : g[v]){
            if(x == p) continue;
            dfs(x, v, d + 1); 
        }
        sort(all(g[v]), [&](int lhs, int rhs){
            return dp[lhs] > dp[rhs];
        });
        for(int x : g[v]){
            if(x == p) 
                continue;
            vect.pb(dp[x]);
        }
        if(vect.size() == 0)
            dp[v] = d;
        else if(vect.size() == 1)
            dp[v] = 1 + d;
        else{
            dp[v] = (int)vect.size() - 1 + vect[1];
        }
    };
    dfs(t, -1, 0); 
    int cum_deg = 0;
    REPD(i, (int)path.size() - 2){
        int v = path[i];
        int nx = (i == 0 ? -1 : path[i - 1]);
        cum_deg += (int)g[v].size() - 2;
        for(int x : g[v]){
            if(x == nx || x == par[v])
                continue;
            if(i != 0)
                dp[x] += cum_deg - 1;
            else
                dp[x] += cum_deg;
        }  
    }
    
    auto check = [&](int maxi){
        int num_blocked = 0;
        int num_max = min(maxi, 1);
        int v = m;
        int pv = -1;
        vector<int> tm;
        int num_blocked_layer = 0;
        while(v != t){
            tm = vector<int>();
            for(int x : g[v]){
                if(x == par[v] || x == pv) 
                    continue;
                tm.pb(dp[x]);
            }
            REP(i, tm.size()){
                if(tm[i] + num_blocked_layer > maxi){
                    if(num_blocked == num_max)
                        return false;
                    num_blocked++;
                } 
            }
            //dbg(v, tm, maxi);
            num_max = min(num_max + 1, maxi);
            pv = v;
            v = par[v];
            num_blocked_layer = num_blocked;
        }
        return true;
    };
    int ans = 0;
    REP(i, 3 * n){
        if(check(i)){
            ans = i;
            break;
        }
    }
    cout << ans << "\n";
    
    return 0;
}

Compilation message

mousetrap.cpp: In lambda function:
mousetrap.cpp:19:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
mousetrap.cpp:21:18: note: in expansion of macro 'FOR'
   21 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
mousetrap.cpp:144:13: note: in expansion of macro 'REP'
  144 |             REP(i, tm.size()){
      |             ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 62964 KB Output is correct
2 Correct 384 ms 56868 KB Output is correct
3 Correct 1119 ms 64044 KB Output is correct
4 Correct 537 ms 32284 KB Output is correct
5 Correct 1168 ms 64036 KB Output is correct
6 Correct 1117 ms 64080 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 404 ms 62964 KB Output is correct
12 Correct 384 ms 56868 KB Output is correct
13 Correct 1119 ms 64044 KB Output is correct
14 Correct 537 ms 32284 KB Output is correct
15 Correct 1168 ms 64036 KB Output is correct
16 Correct 1117 ms 64080 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 431 ms 63156 KB Output is correct
31 Correct 406 ms 62936 KB Output is correct
32 Correct 506 ms 207928 KB Output is correct
33 Correct 472 ms 203956 KB Output is correct
34 Correct 1183 ms 64204 KB Output is correct
35 Correct 1122 ms 64192 KB Output is correct
36 Correct 1178 ms 78668 KB Output is correct
37 Correct 1160 ms 78724 KB Output is correct
38 Correct 916 ms 81372 KB Output is correct
39 Correct 1695 ms 81320 KB Output is correct
40 Correct 945 ms 81304 KB Output is correct