Submission #113599

#	Time	Username	Problem	Language	Result	Execution time	Memory
113599		MladenP	Dreaming (IOI13_dreaming)	C++17	100 / 100	209 ms	16504 KiB

dreaming

#include"dreaming.h"
#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) cerr << #x << '=' << x << endl;
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 100010
vector<int> v, cur;
vector<pair<int,int> > adj[MAXN];
int pos[MAXN], dist1[MAXN], dist2[MAXN], rez;
void DFS1(int node, int prev, int dub, int dist[]) {
    dist[node] = dub;
    for(auto x : adj[node]) {
        if(x.fi != prev) DFS1(x.fi, node, dub+x.se, dist);
    }
}
void DFS2(int node, int prev) {
    pos[node] = 1;
    cur.pb(node);
    for(auto x : adj[node]) {
        if(x.fi != prev) DFS2(x.fi, node);
    }
}
int handle(int node) {
    cur.clear(); int X = MAXN-1, Y = MAXN-1, C = MAXN-1;
    DFS2(node, node);
    DFS1(node, node, 0, dist1);
    for(auto x : cur) if(dist1[x] > dist1[X]) X = x;
    DFS1(X, X, 0, dist1);
    for(auto y : cur) if(dist1[y] > dist1[Y]) Y = y;
    rez = max(rez, dist1[Y]);
    DFS1(Y, Y, 0, dist2);
    dist1[C] = dist2[C] = INF;
    for(auto c : cur) if(max(dist1[c], dist2[c]) < max(dist1[C], dist2[C])) C = c;
    dist1[MAXN-1] = dist2[MAXN-1] = 0;
    return max(dist1[C], dist2[C]);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0; i < M; i++) {
        adj[A[i]].pb({B[i], T[i]});
        adj[B[i]].pb({A[i], T[i]});
    }
    for(int i = 0; i < N; i++) {
        if(!pos[i]) v.pb(handle(i));
    }
    sort(all(v));
    reverse(all(v));
    if(sz(v) >= 2) rez = max(rez, v[0]+v[1]+L);
    if(sz(v) >= 3) rez = max(rez, v[1]+v[2]+L+L);
    return rez;
}
///

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