Submission #859736

#	Time	Username	Problem	Language	Result	Execution time	Memory
859736		Vladth11	Torrent (COI16_torrent)	C++14	100 / 100	148 ms	73420 KiB

torrent

#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 (stderr)

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 / 31
• Subtask 2: 69 / 69