Submission #279836

#	Time	Username	Problem	Language	Result	Execution time	Memory
279836		shayan_p	Dreaming (IOI13_dreaming)	C++14	14 / 100	88 ms	14712 KiB

dreaming

// And you curse yourself for things you never done

#include<bits/stdc++.h>
#include "dreaming.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<pii> v[maxn];

int pr[maxn], prv[maxn], h[maxn];
bool mark[maxn];

int far(int u, int par = -1){
    mark[u] = 1;
    if(par == -1)
	h[u] = 0;
    int ans = u;
    for(pii p : v[u]){
	int y = p.F, c = p.S;
	if(y != par){
	    h[y] = h[u] + c;
	    pr[y] = u;
	    prv[y] = c;
	    int x = far(y, u);
	    if(h[x] > h[ans])
		ans = x;
	}
    }
    return ans;
}

int travelTime(int n, int m, int L, int a[], int b[], int t[]){
    for(int i = 0; i < m; i++){
	v[a[i]].PB({b[i], t[i]});
	v[b[i]].PB({a[i], t[i]});
    }
    int ans = 0;
    vector<int> vec;
    for(int i = 0; i < n; i++){
	if(!mark[i]){
	    int A = far(i), B = far(A);
	    int tmp = B, tmpv = 0, LST = -1;
	    ans = max(ans, h[B]);
	    while(tmpv + tmpv < h[B]){
		LST = prv[tmp];
		tmpv+= prv[tmp];
		tmp = pr[tmp];
	    }
	    tmpv = min(tmpv, h[B] - tmpv + LST);
	    vec.PB(tmpv);
	}
    }
    if(sz(vec) == 1)
	return ans;
    if(sz(vec) == 2)
	return max(ans, vec[0] + vec[1] + L);
    sort(vec.begin(), vec.end());
    int A = vec[sz(vec)-3], B = vec[sz(vec)-2], C = vec[sz(vec)-1];
    return max({ans, L + B + C, L + L + A + B});
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23