Submission #216574

#	Time	Username	Problem	Language	Result	Execution time	Memory
216574		robinrst	Race (IOI11_race)	C++17	0 / 100	10 ms	8960 KiB

race

#include        "algorithm"
#include        "iostream"
#include        "numeric"
#include        "iomanip"
#include        "cstring"
#include        "math.h"
#include        "bitset"
#include        "string"
#include        "vector"
#include        "ctime"
#include        "queue"
#include        "stack"
#include        "map"
#include        "set"

#include        "ext/pb_ds/assoc_container.hpp" // Common file
#include        "ext/pb_ds/tree_policy.hpp" // Including tree_order_statistics_node_update
#include        "ext/pb_ds/detail/standard_policies.hpp"

using namespace std;
using namespace __gnu_pbds;


#define          f first
#define          lgn 25
#define          endl '\n'
#define          sc second
#define          NN (int)2e5+5
#define          pb push_back
#define          mod 1000000007
#define          ld long double
#define          mp make_pair
#define          vi vector<int>
#define          eb emplace_back
#define          vpii vector<pii>
#define          mii map<int,int>
// #define          int long long 
#define          pii pair<int,int>
#define          pq priority_queue
#define          BLOCK (int)sqrt(N)
#define          test(x) while(x--)
#define          all(x) begin(x),end(x)
#define          allr(x) rbegin(x),rend(x)
#define          fo(i,a,n) for(int i=a;i<n;i++)
#define          rfo(i,n,a) for(int i=n;i>=a;i--)
#define          FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define          time() cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n"
#define          PI acos(-1.0)
#define 		 bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)

typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update > 
OS ;

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

inline void INP()
{
	#ifndef ONLINE_JUDGE
	    freopen("input.txt","r",stdin);   
	    freopen("output.txt","w",stdout);
	#endif 
}

const int inf = 0x3f3f3f3f;
// const int INF = 0x3f3f3f3f3f3f3f3f;

int n,m,k,q,nodes,childs, ans;
string s;
vpii adj[NN];
int Dep[NN] , sz[NN] , Q[NN] , temp[NN] , vis[NN] , path[(int)1e6+100];

void Sz(int i = 1, int p = 0)
{
	sz[i] = 1;
	nodes++;

	for( auto j : adj[i] )
	{
		if( j.f != p ) Sz( j.f, i ) , sz[i] += sz[j.f];
	}
}

int getRoot(int i , int p)
{
	for( auto j : adj[i] )
	{
		if( j.f != p and sz[j.f] > nodes/2 )
		{
			return getRoot(j.f ,i);
		}
	}
	return i;
}

void getAllDis(int i , int p , int sum , int dep)
{
	if( sum > m ) return;
	temp[++childs] = sum;
	Dep[childs] = dep;

	for( auto j : adj[i] )
	{
		if( j.f != p )
		{
			getAllDis(j.f , i , sum + j.sc , dep + 1 );
		}
	}
}

void makeAns(int i , int p )
{
	int dn = 0;
	vi rmv;
	for( auto j : adj[i] )
	{
		if( j.f != p and !vis[j.f] )
		{
			childs = 0;
			getAllDis(j.f, i, j.sc , 1);

			rfo(k,childs,1)
			{
				int dis = temp[k];
				if( m >= temp[k] ) 
				{
					ans = min( ans , path[ m - dis] + Dep[k] );
				}
			}
			rfo(k,childs,1)
			{
				rmv.pb( temp[k] );
				path[temp[k]] = min( path[temp[k]] , Dep[k] );
			}
		}
	}
	for( auto j : rmv ) path[j] = inf;
}

void centroidTree(int i = 1, int p = 0 )
{
	nodes = 0;
	Sz(i,i);
	path[0] = 0;

	int centroid = getRoot(i,i);
	makeAns(centroid, 0);

	vis[i] = 1;

	for( auto j : adj[centroid] )
	{
		if( j.f != p and !vis[j.f] )
		{
			centroidTree(j.f , centroid);
		}
	}
}

int go()
{
	// cin >> n >> m;

	// fo(i,0,n-1)
	// {
	// 	int u, v , w;
	// 	cin >> u >> v >> w;
	// 	u++ , v++;
	// 	adj[u].pb({ v, w });
	// 	adj[v].pb({ u, w });
	// }	
	memset( path ,inf , sizeof path );
	ans = inf;
	centroidTree();

	if( ans >= n ) ans = -1;
	
	return ans;
}

int best_path (int N, int K, int H[][2], int L[])
{
    n = N, m = K;
    fo(i,0,n-1)
    {
        adj[H[i][0]].pb(mp(H[i][1], L[i]));
        adj[H[i][1]].pb(mp(H[i][0], L[i]));
    }
    return go();
}

// int32_t main()
// {
// 	INP(); 
// 	FAST;     
// 	int t=1; 
// 	// cin>>t;
// 	test(t) go();
// }

 

Compilation message (stderr)

race.cpp: In function 'void makeAns(int, int)':
race.cpp:119:6: warning: unused variable 'dn' [-Wunused-variable]
  int dn = 0;
      ^~

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