Submission #797799

#	Time	Username	Problem	Language	Result	Execution time	Memory
797799		gg123_pe	Dreaming (IOI13_dreaming)	C++14	100 / 100	59 ms	18052 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h> 
using namespace std; 

#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 1e5 + 5; 

int n; 
int d[N], p[N], W[N]; 
vector <pair<int,int>> adj[N]; 
vector <int> used; 

void dfs(int u, int f){
    used.push_back(u);  
    for(auto pa: adj[u]){
        int v = pa.first, w = pa.second; 
        if(v == f) continue;
        d[v] = d[u] + w; 
        p[v] = u, W[v] = w; 
        dfs(v, u); 
    }
}
pair<int,int> get(int u){
    d[u] = 0, p[u] = -1, W[u] = 0; 
    used.clear(); 
    dfs(u, -1); 
    int node = -1, maxi = -1; 
    for(int u: used){
        if(d[u] > maxi){
            maxi = d[u], node = u; 
        }
    }
    return {node, maxi}; 
}
int travelTime(int Ni, int M, int L, int A[], int B[], int T[]) {
    n = Ni; 

    f(i,0,M){
        adj[A[i]].push_back({B[i], T[i]});  
        adj[B[i]].push_back({A[i], T[i]}); 
    }

    memset(d, -1, sizeof d); 

    int ans = 0; 
    int x = -1, y = -1, z = -1; 

    f(i,0,n){
        if(d[i] != -1) continue; 
        auto ra = get(i); 
        auto ta = get(ra.first);
        int leaf = ta.first, dim = ta.second; 
        int curr = 0, mini = dim; 
        
        ans = max(ans, dim); 

        while(leaf != ra.first){
            curr += W[leaf]; 
            mini = min(mini, max(curr, abs(dim - curr))); 
            leaf = p[leaf]; 
        }
        if(mini > x) z = y, y = x, x = mini; 
        else if(mini > y) z = y, y = mini; 
        else if(mini > z) z = mini; 
    }
    if(y != -1) ans = max(ans, x + y + L); 
    if(z != -1) ans = max(ans, y + z + 2*L); 

    return ans;
}

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