Submission #314173

#	Time	Username	Problem	Language	Result	Execution time	Memory
314173		qiangbao	Torrent (COI16_torrent)	C++98	100 / 100	518 ms	40744 KiB

torrent

// #include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <string>
#include <functional>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <bitset>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>

using namespace std;

#define pb push_back

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;

const ll INF=1000000007;
const ll INFL=1000000000000000007;
const ld INFS=0.00000001;
const ll MOD=1000000007;
const ld PI=3.14159265;

const int dir[4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int dir2[8][2]={{1, 1}, {1, 0}, {1, -1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}};

// CODE

int n, a, b;
vector<int> con[300001];
vector<int> son[300001];
int father[300001];

int dp[300001];
int dp2[300001];
bool evil[300001];

void rec(int x, int nope)
{
    vector<int> need;
    int i;
    
    for(i=0;i<son[x].size();i++)
        rec(son[x][i], nope);
    for(i=0;i<son[x].size();i++){
        int f=son[x][i];
        if(f!=nope)
            need.pb(dp2[f]);
    }
    sort(need.begin(), need.end());
    int cur=1;
    for(i=int(need.size())-1;i>=0;i--)
        dp2[x]=max(dp2[x], need[i]+cur), cur++;
}

int ok(int x)
{
    int i;
    
    for(i=1;i<=n;i++)
        dp2[i]=0;
    int time=0;
    int pos=b, pos2=b;
    while(dp[pos]+time<=x){
        if(dp[pos]+time==x){
            vector<int> need;
            for(i=0;i<son[pos].size();i++){
                int f=son[pos][i];
                if(f!=pos2)
                    need.pb(dp[f]);
            }
            sort(need.begin(), need.end());
            for(i=int(need.size())-1;i>=0;i--){
                int f=need[i];
                if(f+time<x)
                    break;
                time++;
            }
            pos2=pos, pos=father[pos], time++;
        }
        else
            pos2=pos, pos=father[pos], time++;
    }
    rec(a, pos2);
    
    if(dp2[a]<=x)
        return 1;
    return 0;
}

void wk(int x)
{
    vector<int> need;
    int i;
    
    for(i=0;i<son[x].size();i++)
        wk(son[x][i]);
    for(i=0;i<son[x].size();i++){
        int f=son[x][i];
        if(!evil[f])
            need.pb(dp[f]);
    }
    sort(need.begin(), need.end());
    int cur=1;
    for(i=int(need.size())-1;i>=0;i--)
        dp[x]=max(dp[x], need[i]+cur), cur++;
}

void rt(int x, int fa)
{
    int i;
    
    for(i=0;i<con[x].size();i++){
        int f=con[x][i];
        if(f!=fa)
            son[x].pb(f), father[f]=x, rt(f, x);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int i;
    
    cin >> n >> a >> b;
    for(i=1;i<n;i++){
        int x, y;
        cin >> x >> y;
        con[x].pb(y);
        con[y].pb(x);
    }
    
    rt(a, -1);
    int cur=b;
    while(cur!=a)
        evil[cur]=true, cur=father[cur];
    wk(a);
    
    int lo=dp[b], hi=n, m;
    while(lo<hi){
        m=(lo+hi)/2;
        if(!ok(m))
            lo=m+1;
        else
            hi=m;
    }
    
    cout << lo << endl;
    
    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'void rec(int, int)':
torrent.cpp:57:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(i=0;i<son[x].size();i++)
      |             ~^~~~~~~~~~~~~~
torrent.cpp:59:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(i=0;i<son[x].size();i++){
      |             ~^~~~~~~~~~~~~~
torrent.cpp: In function 'int ok(int)':
torrent.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for(i=0;i<son[pos].size();i++){
      |                     ~^~~~~~~~~~~~~~~~
torrent.cpp: In function 'void wk(int)':
torrent.cpp:110:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(i=0;i<son[x].size();i++)
      |             ~^~~~~~~~~~~~~~
torrent.cpp:112:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(i=0;i<son[x].size();i++){
      |             ~^~~~~~~~~~~~~~
torrent.cpp: In function 'void rt(int, int)':
torrent.cpp:127:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(i=0;i<con[x].size();i++){
      |             ~^~~~~~~~~~~~~~

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