oj.uz

Submission #859736

# Submission time Handle Problem Language Result Execution time Memory
859736 2023-10-10T15:02:50 Z Vladth11 Torrent (COI16_torrent) C++14
100 / 100
 148 ms 73420 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const ll NMAX = 300002;
const ll INF = (1LL << 60);
const ll nrbits = 20;
const ll MOD = 998244353;
const ll bucket = 320;
const double eps = 0.00000001;

vector <int> banned, stiva;
vector <int> v[NMAX];
map <int, int> mp[NMAX];

int ban[NMAX], b, a;
int dp[NMAX];
int pa[NMAX];
int vechi[NMAX];
int bad[NMAX];
set <int> rele[NMAX];

void DFS(int node, int p){
    pa[node] = p;
    if(node == b){
        banned = stiva;
        for(auto x : stiva){
            ban[x] = 1;
        }
    }
    if(node != a)
        stiva.push_back(node);
    for(auto x : v[node]){
        if(x == p) continue;
        DFS(x, node);
    }
    if(node != a)
        stiva.pop_back();
}

int recalculeaza(int node){
    if(mp[node].size() == 0) return 0;
    int nasol = 0, acu = 0;
    vector <pii> hk;
    for(auto x : mp[node]){
        hk.push_back({x.first, x.second});
    }
    reverse(hk.begin(), hk.end());
    for(auto x : hk){
        if(bad[node] < x.first + x.second + acu){
            bad[node] = x.first + x.second + acu;
            rele[node].clear();
            rele[node].insert(x.first);
        }else if(bad[node] == x.first + x.second + acu){
            rele[node].insert(x.first);
        }
        acu += x.second;
    }
    return bad[node];
}

int calculeaza(int node, int nou){
    int nasol = bad[node];
    if(rele[node].find(nou) != rele[node].end()){
        nasol++;
    }
    nasol = max(nasol, nou + 1);
    return nasol;
}

void DFS1(int node, int p){
    vector <int> s;
    for(auto x : v[node]){
        if(x == p) continue;
        DFS1(x, node);
        if(ban[x] == 0 && x != a && x != b)
            mp[node][dp[x]]++;
    }
    dp[node] = vechi[node] = recalculeaza(node);
}

void sterge(int a, int b){
    mp[a][b]--;
    if(mp[a][b] == 0){
        mp[a].erase(b);
    }
}

int f(int unde){
    int ultim = -1;
    if(unde != -1){
        ultim = banned[unde];
    }
    for(int i = unde - 1; i >= 0; i--){
        int x = banned[i + 1];
        int node = banned[i];
        dp[node] = calculeaza(node, dp[x]);
        ultim = node;
    }
    if(ultim != -1){
        dp[b] = calculeaza(b, dp[ultim]);
    }
    ultim = -1;
    if(unde + 1 != banned.size()){
        ultim = banned[unde + 1];
    }
    for(int i = unde + 2; i < banned.size(); i++){
        int x = banned[i - 1];
        int node = banned[i];
        dp[node] = calculeaza(node, dp[x]);
        ultim = node;
    }
    if(ultim != -1){
        dp[a] = calculeaza(a, dp[ultim]);
    }
    int sol = max(dp[a], dp[b]);
    for(auto x : banned){
        dp[x] = vechi[x];
    }
    dp[a] = vechi[a];
    dp[b] = vechi[b];
    return sol;
}

int ternary(int st, int dr){
    if(st + 1 >= dr){
        return min(f(st), f(dr));
    }
    int mid = st + (dr - st) / 3;
    int mid1 = dr - (dr - st) / 3;
    if(f(mid) > f(mid1)){
        return ternary(mid + 1, dr);
    }
    return ternary(st, mid1 - 1);
}

signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, i;
    cin >> n >> a >> b;
    for(i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    DFS(a, 0);
    DFS1(a, 0);
    reverse(banned.begin(), banned.end());
    cout << ternary(-1, banned.size() - 1);

    return 0;
}

Compilation message

torrent.cpp: In function 'int recalculeaza(int)':
torrent.cpp:48:9: warning: unused variable 'nasol' [-Wunused-variable]
   48 |     int nasol = 0, acu = 0;
      |         ^~~~~
torrent.cpp: In function 'int f(int)':
torrent.cpp:109:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     if(unde + 1 != banned.size()){
      |        ~~~~~~~~~^~~~~~~~~~~~~~~~
torrent.cpp:112:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i = unde + 2; i < banned.size(); i++){
      |                           ~~^~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 41564 KB Output is correct
2 Correct 8 ms 41608 KB Output is correct
3 Correct 8 ms 41564 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 63844 KB Output is correct
2 Correct 133 ms 68688 KB Output is correct
3 Correct 136 ms 69752 KB Output is correct
4 Correct 139 ms 72764 KB Output is correct
5 Correct 148 ms 71408 KB Output is correct
6 Correct 137 ms 71508 KB Output is correct
7 Correct 134 ms 73420 KB Output is correct