oj.uz

Submission #559335

# Submission time Handle Problem Language Result Execution time Memory
559335 2022-05-09T15:43:48 Z fatemetmhr Mousetrap (CEOI17_mousetrap) C++17
25 / 100
 782 ms 60128 KB 
// Be name khoda //

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define pb       push_back
 
const int maxn5 = 1e6 + 10;
const int inf   = 1e9;
 
int tale, mo, dp[maxn5], id[maxn5];
int htotale[maxn5], fen[maxn5];
vector <int> adj[maxn5], ver;
vector <pair<int, int>> av;
 
inline bool dfs(int v, int par){
    if(v == tale){
        dp[v] = 0;
        htotale[v] = 0;
        return true;
    }
    int mx = 0, smx = 0;
    int z = -1;
    for(auto u : adj[v]) if(u != par){
        bool re = dfs(u, v);
        if(re){
            z = u;
        }
        if(dp[u] >= mx){
            smx = mx;
            mx = dp[u];
        }
        else
            smx = max(smx, dp[u]);
    }
    if(z == -1){
        dp[v] = smx + adj[v].size() - 1;
        //cout << "false " << v << ' ' << dp[v] << endl;
        return false;
    }
 
    htotale[v] = htotale[z] + adj[v].size() - 2 + (v == mo);
    for(auto u : adj[v]) if(u != par && u != z){
        av.pb({dp[u] + htotale[v], v});
        //cout << "aha " << v << ' ' << u << ' ' << dp[u] << ' ' << htotale[v] << endl;
    }

    ver.pb(v);
    return true;
}

inline void add(int id){
    for(; id < maxn5; id += id & -id)
        fen[id]++;
}
inline int get(int id){
    int ret = 0;
    for(; id; id -= id & -id)
        ret += fen[id];
    return ret;
}
inline bool ok(int v){
    v = id[v];
    return get(v) < v;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    int n, a, b; cin >> n >> a >> b;
    a--; b--;
    mo = b;
    tale = a;
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        a--; b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
 
    assert(a != b);
 
    if(a == b)
        return cout << 0 << endl, 0;
 
    dfs(mo, -1);

    reverse(all(ver)); // az m be t hast
    assert(ver.size() == 1);

    int pos = 1;
    for(auto v : ver){
        id[v] = pos++;
    }
    sort(all(av));
    reverse(all(av));
    int done = 0;
    int mx = 0;
    int ans = inf;
    for(auto [val, v] : av){
        assert(done <= 1);
        //cout << "& " << val << ' ' << v << endl;
        ans = min(ans, val);
        if(ok(v)){
            done++;
            add(id[v]);
        }
        else
            break;
    }
    cout << ans << endl;
}

Compilation message

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:104:9: warning: unused variable 'mx' [-Wunused-variable]
  104 |     int mx = 0;
      |         ^~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 48112 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 59064 KB Output is correct
2 Correct 317 ms 55628 KB Output is correct
3 Correct 734 ms 60128 KB Output is correct
4 Correct 353 ms 41916 KB Output is correct
5 Correct 782 ms 60124 KB Output is correct
6 Correct 762 ms 60084 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 48112 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 48112 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -