oj.uz

답안 #559365

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559365 2022-05-09T16:29:37 Z fatemetmhr Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 295 ms 58980 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 maxnt = 5e6 + 10;
const int inf   = 1e9;
 
int tale, mo, dp[maxn5], id[maxn5], newid = 0;
int htotale[maxn5], st[maxn5], parr[maxn5];
int valu[maxn5], valval[maxn5], zz[maxn5];
int cmp[maxn5];
vector <int> adj[maxn5], ver;
vector <pair<int, int>> av;
pair <int, int> mx[maxnt];
int mn[maxnt], lazy[maxnt], lazy2[maxnt];

inline void build(int l, int r, int v){
    if(r - l == 1){
        mx[v] = {valu[l], l};
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, v * 2);
    build(mid, r, v * 2 + 1);
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
    return;
}

inline void build2(int l, int r, int v){
    if(r - l == 1){
        mn[v] = valval[l];
        return;
    }
    int mid = (l + r) >> 1;
    build2(l, mid, v * 2);
    build2(mid, r, v * 2 + 1);
    mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
    return;
}

inline void add2(int l, int r, int lq, int rq, int v){
    if(rq <= l || r <= lq)
        return;
    if(lq <= l && r <= rq){
        mn[v]--;
        lazy2[v]--;
        return;
    }
    int mid = (l + r) >> 1;
    add2(l, mid, lq, rq, v * 2);
    add2(mid, r, lq, rq, v * 2 + 1);
    mn[v] = max(mn[v * 2], mn[v * 2 + 1]) + lazy2[v];
    return;
}

inline void add(int l, int r, int lq, int rq, int val, int v){
    if(rq <= l || r <= lq)
        return;
    if(lq <= l && r <= rq){
        mx[v].fi += val;
        lazy[v] += val;
        return;
    }
    int mid = (l + r) >> 1;
    add(l, mid, lq, rq, val, v * 2);
    add(mid, r, lq, rq, val, v * 2 + 1);
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
    mx[v].fi += lazy[v];
    return;
}

 
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);
    ver.pb(v);
    parr[v] = par;
    zz[v] = z;

    //ft[ver.size()] = newid;

    return true;
}


inline bool ok(int v){
    //assert(v == 1);
    add2(0, ver.size() + 1, v, ver.size() + 1, 1);
    return mn[1] >= 0;
}
 
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 mxx = 0, smx = 0;
    int pos = 1;
    for(auto v : ver){
        for(auto u : adj[v]) if(u != parr[v] && u != zz[v]){
            cmp[newid] = pos;
            valu[newid++] = dp[u] + htotale[v];
            if(mxx <= dp[u] + htotale[v]){
                smx = mxx;
                mxx = dp[u] + htotale[v];
            }
            else
                smx = max(smx, dp[u] + htotale[v]);
            //cout << "aha " << v << ' ' << u << ' ' << dp[u] << ' ' << htotale[v] << endl;
        }
        st[pos] = newid;
        pos++;
    }

    //return cout << min(inf, smx) << endl, 0;

    
    build(0, newid, 1);
    for(int i = 1; i <= ver.size(); i++)
        valval[i] = i;
    build2(0, ver.size() + 1, 1);

    int done = 0;
    int ans = inf;
    assert(st[pos - 1] == newid);
    while(true && mx[1].fi > -inf){
        int z = mx[1].se;
        //assert(done <= 1);
        ans = min(ans, mx[1].fi + done);
        //if(done == 1)
            //assert(mx[1].fi + done == smx);
        //if(done == 0)
            //assert(mx[1].fi == mxx);
        if(ok(cmp[z])){
            done++;
            //assert(st[cmp[z]] == newid);
            add(0, newid, 0, st[cmp[z]], -1, 1);
            add(0, newid, z, z + 1, -inf, 1);
        }
        else
            break;
    }
    //assert(done == 1);
    cout << ans << endl;
}

Compilation message

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

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Incorrect 14 ms 23828 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 295 ms 58980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Incorrect 14 ms 23828 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Incorrect 14 ms 23828 KB Output isn't correct
3 Halted 0 ms 0 KB -