Submission #859728

#	Time	Username	Problem	Language	Result	Execution time	Memory
859728		Vladth11	Torrent (COI16_torrent)	C++14	0 / 100	56 ms	45940 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 <ll, ll> pii;

const ll NMAX = 200002;
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];

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 calculeaza(int node){
    if(mp[node].size() == 0) return 0;
    int nasol = 0;
    for(auto x : mp[node]){
        nasol = max(nasol, x.first + x.second);
    }
    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] = calculeaza(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];
        mp[node][dp[x]]++;
        dp[node] = calculeaza(node);
        ultim = node;
    }
    if(ultim != -1){
        mp[b][dp[ultim]]++;
        dp[b] = calculeaza(b);
    }
    int sol = dp[b];
    if(ultim != -1){
        sterge(b, dp[ultim]);
        dp[b] = calculeaza(b);
    }
    for(int i = 0; i < unde; i++){
        int x = banned[i + 1];
        int node = banned[i];
        sterge(node, dp[x]);
        dp[node] = calculeaza(node);
    }
    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];
        mp[node][dp[x]]++;
        dp[node] = calculeaza(node);
        ultim = node;
    }
    if(ultim != -1){
        mp[a][dp[ultim]]++;
        dp[a] = calculeaza(a);
    }
    sol = max(sol, dp[a]);
    if(ultim != -1){
        sterge(a, dp[ultim]);
        dp[a] = calculeaza(a);
    }
    for(int i = banned.size() - 1; i >= unde + 2; i--){
        int x = banned[i - 1];
        int node = banned[i];
        sterge(node, dp[x]);
        dp[node] = calculeaza(node);
    }
    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());
    int minim = 2e9;
    for(i = (-1) + 1; i < banned.size() + 1; i++){
        vechi[i] = f(i - 1);
        minim = min(minim, vechi[i]);
    }
    cout << minim;

    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int f(int)':
torrent.cpp:99:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     if(unde + 1 != banned.size()){
      |        ~~~~~~~~~^~~~~~~~~~~~~~~~
torrent.cpp:102:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = unde + 2; i < banned.size(); i++){
      |                           ~~^~~~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:159:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for(i = (-1) + 1; i < banned.size() + 1; i++){
      |                       ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69