Submission #1003499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003499		_rain_	Race (IOI11_race)	C++14	0 / 100	10 ms	23900 KiB

race

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using ui64 = unsigned long long;

#define MASK(x) ((i64)(1) << (x))
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define sz(x) (x).size()
#define all(x) (x).begin() , (x).end()

#define FOR(i ,a , b) for (int i = (a); i <= (b); ++i)
#define FORD(i , a , b) for (int i = (b); i >= (a); --i)
#define REP(i , a , b) for (int i = (a); i < (b); ++i)
#define REPD(i , a , b) for (int i = (b) - 1 ; i >= (a); --i)

template <class T> 
    void compress(vector<T> &a)
    {
        sort(a.begin() , a.end());
        a.resize(unique(a.begin() , a.end()) - a.begin());
        return;
    }
template<class T>
    void printArr(T& container , string separator = "" , string finish = "\n")
    {
        for (auto& item : container) cout << item << separator;
        cout << finish;
    }
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template<class T>
    bool maximize(T &a , T b) {if (a < b) return a = b , true; else return false;}
template<class T>
    bool minimize(T &a , T b) {if (a > b) return a = b , true; else return false;}
template<class T>
    T gcd(T x , T y) {while (y) swap(y , x %= y); return x;}
template<class T>
    T lcm(T x , T y) {return (x * y) / gcd(x , y);}

const int maxn = 1e6;
int cnt[maxn + 2];
bool del[maxn + 2];
int sub[maxn + 2];
vector<pair<int,int>>g[maxn+2];
int n,k;

int find_centroid(int u , int p , int half)
{
	for (auto& v : g[u])
	{
		if (del[v.first])continue;
		if(v.first!=p&&sub[v.first]>half)return find_centroid(v.first,u,half);
	}
	return u;
}
void dfs_size(int u , int p)
{
	sub[u] = 1;
	for(auto&v:g[u])
		if (v.first!=p&&!del[v.first])
		{
			dfs_size(v.first,u);
			sub[u]+=sub[v.first];
		}
	return;
}
int maxh=0;
int answer=1e9+7;

void calc(int d,int h , int u , int p , int t)
{
	maxh=max(maxh,h);
	if (t)
		minimize(cnt[h],d);
	else 
	{
		if(k-h>=0&&(i64)d+cnt[k-h]<=(int)1e9+7)
		 	minimize(answer,d+cnt[k-h]);
	}
	for (auto& v : g[u])
		if (!del[v.first]&&v.first!=p&&h+v.second<=k)
			calc(d+1,h+v.second,v.first,u,t);
	return;
}

void build(int u)
{
	dfs_size(u,u);
	u=find_centroid(u,u,sub[u]/2);
	maxh=0;
	del[u]=true;
	cnt[0]=0;
	for (auto& v : g[u])
	{
		if (del[v.first]) continue;
		calc(1,v.second,v.first,u,0);
		calc(1,v.second,v.first,u,1);
	}
	memset(cnt,0x3f,sizeof(int)*(maxh+2));
	for(auto& v : g[u])
		if (!del[v.first]) build(v.first);
	return;
}

int best_path(int N, int K, int H[][2], int L[])
{
	k = K;
  	REP(i,0,N-1)
  	{
  		H[i][0]++;
  		H[i][1]++;
  		g[H[i][0]].push_back({H[i][1],L[i]});
  		g[H[i][1]].push_back({H[i][0],L[i]});
  	}
  	build(1);
  	N = (answer>=(int)1e9+7?-1:answer);
	return N;
}

// int32_t main()
// {
//     iostream::sync_with_stdio(false); cin.tie(0);
//     const string name = "main";
//     if (fopen((name + ".inp").c_str() , "r"))
//     {
//         (void)!freopen((name + ".inp").c_str() , "r" , stdin);
//         (void)!freopen((name + ".out").c_str() , "w+", stdout);
//     }
//     memset(cnt,0x3f,sizeof cnt);
//     cin>>n>>k;
//     REP(i,1,n)
//     {
//     	int u,v,h;cin>>u>>v>>h;
//     	++u,++v;
//     	g[u].push_back({v,h});
//     	g[v].push_back({u,h});
//     }
    
//     cout<<(answer>=(int)1e9+7?-1:answer);
// }

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