Submission #932325

#	Time	Username	Problem	Language	Result	Execution time	Memory
932325		kxd	Shortcut (IOI16_shortcut)	C++17	0 / 100	2 ms	5724 KiB

shortcut

#define tj
#ifdef tj
#include "shortcut.h"
#endif
#include <bits/stdc++.h>
//#define DEBUG 1106
//#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define p_q priority_queue
#define m_p make_pair
#define pii pair<int,int>
#define endl '\n'
#define INIT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define forn(i,n) for (int i = 0; i < n; i++)
#define forn1(i,n) for (int i = 1; i <= n; i++)
#define all(x) x.begin(),x.end()
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#ifdef DEBUG
#define debug(x) cout << #x << ": " << x << endl;
#else
#define debug(x) 1106;
#endif

using namespace std;
const int N = 2e5+5;
const int inf = 1e9;
const int INF = 1e18;
const int MOD = 1e9+7;

int n;
vector<pii> G[N];
int dis[N];

long long dfs(int x, int par) {
	int mxi = x;
	for (auto p: G[x]) {
		int v = p.ft;
		int d = p.sd;
		if(v==par||dis[v]!=-1) continue;
		dis[v] = dis[x]+d;
		int t = dfs(v,x); 
		if(dis[t]>dis[mxi]) mxi = t;
	}
	return mxi;
}

long long find_diameter() {
	memset(dis,-1,sizeof(dis));
	dis[0] = 0;
	int u = dfs(0,-1);
	memset(dis,-1,sizeof(dis));
	dis[u] = 0;
	int v = dfs(u,-1);
	return dis[v];
}

long long find_shortcut(int n_, vector<int> l, vector<int> d, int c) {
    n = n_;
    forn(i,n-1) {
    	G[i].pb({i+1,l[i]});
    	G[i+1].pb({i,l[i]});
    	if(d[i]) {
    		G[i].pb({i+n,d[i]});
    		G[i+n].pb({i,d[i]});
		}
	}
	ll ans = INF;
	for(int i = 0; i < n-1; i++) {
		for(int j = i+1; j <= n-1; j++) {
			G[i].pb({j,c});
			G[j].pb({i,c});
			ll t = find_diameter();
			chmin(ans,t);
			G[i].pop_back();
			G[j].pop_back();
		}
	}
	return ans;
}
#ifndef tj
int main() {
    int n, c;
    assert(2 == scanf("%d%d", &n, &c));
    
    std::vector<int> l(n - 1);
    std::vector<int> d(n);
    for (int i = 0; i < n - 1; i++)
        assert(1 == scanf("%d", &l[i]));
    for (int i = 0; i < n; i++)
        assert(1 == scanf("%d", &d[i]));
    long long t = find_shortcut(n, l, d, c);
    printf("%lld\n", t);
    
    return 0;
}
#endif

Compilation message (stderr)

shortcut.cpp:34:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   34 | const int INF = 1e18;
      |                 ^~~~

• 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