Submission #103644

#	Time	Username	Problem	Language	Result	Execution time	Memory
103644		CPX	Race (IOI11_race)	C++14	0 / 100	8 ms	6272 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define setDP(arr) memset(arr,-1,sizeof arr)
#define Clear(arr) memset(arr,0,sizeof arr)
#define oo 1000000000
#define inf 1000000000000000000
#define P1 31
#define P2 37
#define M  1000000007
#define M2 1000000009
#define pii pair<ll,ll>
typedef long long ll;
using namespace std;
const int N = 255001;
const int SQRTN = 320;
const int LOGN = 20;
const long double PI = acos(-1);
const long double TAU = 2*PI;

int n , k,ans = oo,h[100][2],l[100],sz;
vector<pair<int,int> > g[N];
bool vis[N];
vector<int> centroid,v;
map<int,vector<int> > mp;
map<int,vector<int> >::iterator it;
int getSize(int n , int p=-1){
    int ret = 1;
    for(int i = 0 ; i < g[n].size() ; i++){
        if(vis[g[n][i].F]||g[n][i].F==p)continue;
        ret+=getSize(g[n][i].F,n);
    }
    return ret;
}
int getCentroid(int node = 0, int p = -1){
    bool f = 1;
	int s = 1,t;
	for(int i=0;i<g[node].size();i++){
		if (g[node][i].F == p || vis[g[node][i].F])continue;
		t=getCentroid(g[node][i].F,node);
		if(t>sz>>1)
            f = 0;
		s += t;
	}
	if((sz - s)<<1 >sz)f = 0;
	if(f)centroid.push_back(node);
	return s;
}

void dfs(int node, int d1=0, int d2=0 , int p=-1){
    mp[d1].push_back(d2);
    for(int i = 0 ; i < g[node].size() ; i++){
        if(g[node][i].F==p||vis[g[node][i].F])continue;
        dfs(g[node][i].F,d1+g[node][i].S,d2+1,node);
    }
}

void calc(){
    int x=0;
    for(it = mp.begin() ; it != mp.end() ; it++){
        sort(all(it->S));
    }
    for(it = mp.begin() ; it != mp.end() ; it++){
        x=it->F;
        if((x<<1)>k)break;
        if(mp.find(k-x)==mp.end())continue;
        if(k==(x<<1)){
            if((it->S).size()>1){
                ans = min(ans,(it->S)[0]+(it->S)[1]);
            }
        }else{
            ans=min(ans,(it->S)[0]+mp[k-x][0]);
        }
    }
}

void centroidDecomposiotion(int node = 0){
    sz = getSize(node);
    if(sz==1)return;
    getCentroid(node);
    int root = centroid[0];
    centroid.clear();
    dfs(root);
    calc();
    mp.clear();
    vis[root]=1;
    for(int i = 0 ; i < g[root].size() ; i++){
        if(!vis[g[root][i].F])
            centroidDecomposiotion(g[root][i].F);
    }
}


int best_path(int n , int k , int h[][2], int l[]){
    ::n = n;
    ::k = k;
    for(int i = 0 ; i < n-1 ; i++){
        g[h[i][0]].push_back(make_pair(h[i][1],l[i]));
        g[h[i][1]].push_back(make_pair(h[i][0],l[i]));
    }
    centroidDecomposiotion(0);
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'int getSize(int, int)':
race.cpp:31:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < g[n].size() ; i++){
                     ~~^~~~~~~~~~~~~
race.cpp: In function 'int getCentroid(int, int)':
race.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
              ~^~~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < g[node].size() ; i++){
                     ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'void centroidDecomposiotion(int)':
race.cpp:89:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < g[root].size() ; i++){
                     ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57