Submission #1241560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241560		papaulo	Dreaming (IOI13_dreaming)	C++20	0 / 100	30 ms	13376 KiB

dreaming

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

using namespace std;

#define MAXN 100100
int dist[MAXN];
int visited[MAXN];
int far;
int pai[MAXN];

vector<pair<int, int>> adj[MAXN];

void dfs(int v, int p) {
    visited[v]=1;
    pai[v]=p;
    if(dist[v]>dist[far]) far=v;
    for(auto e : adj[v]) {
        if(e.first==p) continue;
        dist[e.first]=dist[v]+e.second;
        dfs(e.first, v);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    memset(visited, 0, sizeof(visited));
    for(int i=0;i<M;i++) {
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }
    vector<int> trees;
    for(int i=0;i<N;i++) {
        if(visited[i]) continue;
        dist[i]=0;
        far=i;
        dfs(i, -1);
        dist[far]=0;
        dfs(far, -1);
        int v=far;
        int bst=1e9;
        while(v!=-1) {
            bst=min(bst, max(dist[v], dist[far]-dist[v]));
            v=pai[v];
        }
        trees.push_back(bst);
    }
    sort(trees.rbegin(), trees.rend());
    deque<int> dq;
    for(int i=0;i<trees.size();i++) {
        int t=trees[i];
        if(i%2==0) dq.push_back(t);
        else dq.push_front(t);
    }
    int ans=0;
    int curFar=0;
    for(auto t : dq) {
        ans=max(ans, t+curFar);
        curFar=max(curFar, t)+L;
    }
    return ans;
}

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