Submission #133026

#	Time	Username	Problem	Language	Result	Execution time	Memory
133026		wzy	Shortcut (IOI16_shortcut)	C++11	0 / 100	2 ms	504 KiB

shortcut

// cancer problem D: 
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,long long>
#define F first
#define S second
#define pb push_back
const int N = 3003;
typedef long long ll;
ll dist[N][N];
vector<pii> adj[N];
ll diametro[N][N];
int n;
vector<int> passa;
int pai[N];
ll dp[N];
ll g[N];

int cx[N];
void fill_dist(int i , int p , int d , int r){
	dist[r][i] = d;
	for(auto w : adj[i]){
		if(p != w.F){
			fill_dist(w.F , i , d +w.S , r);
		}
	}
}

void diam(int x , int p , int bl1 , int bl2 ){
	for(auto w : adj[x]){
		if(w.F == p || w.F == bl1 || w.F == bl2) continue;
		diam(w.F , x , bl1 , bl2);
		dp[x] = max(max(dp[w.F] , g[x] + w.S + g[w.F]) , dp[x]);
		g[x] = max(g[w.F] + w.S , g[x]);
	}
}

void dfs(int x , int p){
	pai[x] = p;
	for(auto w : adj[x]){
		if(w.F != p){
			dfs(w.F , x);
		}
	}
}

ll solve(int x , int y , int c){
	dfs(x , -1);
	int u = y;
	vector<pii> v;
	for(int i = 0 ; i < n ; i ++){
		cx[i] = 0 ;
		g[i] = 0 , dp[i] = 0;
	}
	while(u != -1){
		int d = 0;
		if(u == x){
			d = 0;
		}
		else{
			d = dist[pai[u]][u];
		}
		v.push_back(pii(u , d));
		u = pai[u];
	}
	reverse(v.begin() ,v.end());
	ll ans = 0;
	for(int i = 0 ; i < v.size() ;i  ++){
		int x1 = v[(i+1)%v.size()].F;
		int x2 = v[(i-1 + v.size())%v.size()].F;
		int L = -1;
		for(auto w : adj[v[i].F]){
			if(w.F != x1 && w.F != x2){
				L = w.F;
			}	
		}
		if(L != -1){
			diam(v[i].F , -1 , x1 , x2);
			ans = max(ans , dp[v[i].F]);
		}
 		if(L != -1)
		cx[v[i].F] = g[v[i].F];
		if(i > 0){
			v[i].S += v[i-1].S;
		}
	}
	int r = 0;
	int S = v.back().S + c;

	for(int i = 0 ; i < v.size() ; i ++){
		if(r%v.size() == i){
			r++;
		}
		while((r+1)%v.size() != i && (min(S - abs(v[i].S - v[r%v.size()].S) , abs(v[i].S - v[(r)%v.size()].S)) + cx[v[r%v.size()].F] + cx[v[i].F]) < (min(S - abs(v[i].S - v[(r+1)%v.size()].S) , abs(v[i].S - v[(r+1)%v.size()].S)) + cx[v[(r+1)%v.size()].F] + cx[v[i].F]) ){
			r++;
			ans = max(ans , min(S - abs(v[i].S - v[r%v.size()].S) , abs(v[i].S - v[(r)%v.size()].S)) + cx[v[r%v.size()].F] + cx[v[i].F]);		
		}
			ans = max(ans , min(S - abs(v[i].S - v[r%v.size()].S) , abs(v[i].S - v[(r)%v.size()].S)) + cx[v[r%v.size()].F] + cx[v[i].F]);		
	}
	return ans;
}


long long find_shortcut(int nx, std::vector<int> l, std::vector<int> d, int c)
{
	n = nx;
	for(int i = 0 ; i < n-1; i ++){
		adj[i].push_back(pii(i+1 , l[i]));
		adj[i+1].push_back(pii(i , l[i]));
	}
	for(int i = 0 ; i < nx; i ++){
		if(d[i] != 0){
			n;
			adj[n].push_back(pii(i,  d[i]));
			adj[i].push_back(pii(n , d[i]));
			n++;
		}
	}
	for(int i = 0 ; i < n; i ++){
		for(int j = 0 ; j < n ; j ++) dist[i][j] = (ll) 1e18;
		dist[i][i] = 0;
		fill_dist(i , -1 , 0 , i);
	}

	ll p = 0;
	for(int i = 0 ; i < n ; i ++)
		for(int j = 0 ; j < n ; j ++){
			p = max(p , dist[i][j]);
		}
	// cout<<p<<endl;
	for(int i = 0 ; i < nx ; i ++){
		for(int j = i+1 ; j < nx ; j ++){
			p = min(p , solve(i, j , c));
			// cout<<solve(i,j,c)<<" " <<i <<" " <<j <<" " << endl;
		}
	}
	return p;
}

Compilation message (stderr)

shortcut.cpp: In function 'll solve(int, int, int)':
shortcut.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < v.size() ;i  ++){
                  ~~^~~~~~~~~~
shortcut.cpp:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < v.size() ; i ++){
                  ~~^~~~~~~~~~
shortcut.cpp:92:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(r%v.size() == i){
      ~~~~~~~~~~~^~~~
shortcut.cpp:95:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while((r+1)%v.size() != i && (min(S - abs(v[i].S - v[r%v.size()].S) , abs(v[i].S - v[(r)%v.size()].S)) + cx[v[r%v.size()].F] + cx[v[i].F]) < (min(S - abs(v[i].S - v[(r+1)%v.size()].S) , abs(v[i].S - v[(r+1)%v.size()].S)) + cx[v[(r+1)%v.size()].F] + cx[v[i].F]) ){
         ~~~~~~~~~~~~~~~^~~~
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:114:5: warning: statement has no effect [-Wunused-value]
    n;
     ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3