oj.uz

Submission #109242

# Submission time Handle Problem Language Result Execution time Memory
109242 2019-05-05T17:51:22 Z updown1 Dreaming (IOI13_dreaming) C++17
0 / 100
 71 ms 13304 KB 
/*
- find a node x in each component such that the max distance from x to a leaf
is minimized
- connect the x's from all the components to the x in the biggest component
- ans = max(path in one component, biggest depth + 2nd biggest depth + L, 2nd biggest depth + 3rd biggest depth + 2*L
*/
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const ll MAXN = 100000, MAX_N = 100000, INF = 1000000000000000000;
//500,000,000 operations
ll farund[MAXN], far2[MAXN], out, sm;
pair<ll, ll> far1[MAXN]; /// (value, child)
vector<ll> vals;
bool vis[MAXN];
vector<pair<ll, ll> > adj[MAXN];

void go1(ll at) {
    if (vis[at]) return;
    vis[at] = true;
    for (auto i: adj[at]) if (!vis[i.a]) {
        go1(i.a);
        farund[at] = max(farund[at], i.b+farund[i.a]);
    }
}
void go2(ll at, ll p, ll d) {
    if (vis[at]) return;
    vis[at] = true;
    for (auto i: adj[at]) if (i.a != p) {
        ll len = farund[i.a] + i.b;
        if (len > far1[at].a) {
            far2[at] = far1[at].a;
            far1[at] = mp(len, i.a);
        }
        else if (len > far2[at]) far2[at] = len;
    }
    if (at != p) {
        ll up;
        if (far1[p].b == at) up = far2[p]+d;
        else up = far1[p].a + d;
        if (up > far1[at].a) {
            far2[at] = far1[at].a;
            far1[at] = mp(up, p);
        }
        else if (up > far2[at]) far2[at] = up;
        //w<< "up" s at c up<<e;
    }
    for (auto i: adj[at]) if (i.a != p) go2(i.a, at, i.b);
}
void go3(ll at) {
    if (vis[at]) return;
    vis[at] = true;
    sm = min(sm, far1[at].a);
    for (auto i: adj[at]) go3(i.a);
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    ffj {
        ll a = A[j], b = B[j], d = T[j];
        adj[a].emplace_back(b, d);
        adj[b].emplace_back(a, d);
    }
    ffi go1(i);
    ffi vis[i] = false;
    ffi go2(i, i, 0);
    //ffi w<< i c far1[i].a<<e;
    ffi out = max(out, far1[i].a);
    ffi vis[i] = false;
    ffi if (!vis[i]) {
        sm = INF;
        go3(i);
        vals.pb(sm);
    }
    while (vals.size() < 3) vals.pb(0);
    sort(vals.begin(), vals.end());
    reverse(vals.begin(), vals.end());
    out = max(out, max(vals[0]+vals[1]+L, vals[1]+vals[2]+2*L));
    return out;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 13304 KB Output is correct
2 Correct 71 ms 13148 KB Output is correct
3 Correct 48 ms 10488 KB Output is correct
4 Correct 12 ms 4224 KB Output is correct
5 Correct 10 ms 3840 KB Output is correct
6 Correct 18 ms 5248 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 13304 KB Output is correct
2 Correct 71 ms 13148 KB Output is correct
3 Correct 48 ms 10488 KB Output is correct
4 Correct 12 ms 4224 KB Output is correct
5 Correct 10 ms 3840 KB Output is correct
6 Correct 18 ms 5248 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 13304 KB Output is correct
2 Correct 71 ms 13148 KB Output is correct
3 Correct 48 ms 10488 KB Output is correct
4 Correct 12 ms 4224 KB Output is correct
5 Correct 10 ms 3840 KB Output is correct
6 Correct 18 ms 5248 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8800 KB Output is correct
2 Correct 35 ms 8660 KB Output is correct
3 Correct 34 ms 8832 KB Output is correct
4 Correct 33 ms 8756 KB Output is correct
5 Correct 31 ms 8696 KB Output is correct
6 Correct 41 ms 9460 KB Output is correct
7 Correct 42 ms 8952 KB Output is correct
8 Correct 33 ms 8568 KB Output is correct
9 Correct 34 ms 8572 KB Output is correct
10 Correct 31 ms 8948 KB Output is correct
11 Correct 4 ms 2688 KB Output is correct
12 Correct 11 ms 6520 KB Output is correct
13 Correct 11 ms 6904 KB Output is correct
14 Correct 10 ms 6392 KB Output is correct
15 Correct 10 ms 6648 KB Output is correct
16 Correct 9 ms 6008 KB Output is correct
17 Correct 8 ms 4600 KB Output is correct
18 Correct 11 ms 7032 KB Output is correct
19 Correct 10 ms 6136 KB Output is correct
20 Incorrect 3 ms 2688 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 13304 KB Output is correct
2 Correct 71 ms 13148 KB Output is correct
3 Correct 48 ms 10488 KB Output is correct
4 Correct 12 ms 4224 KB Output is correct
5 Correct 10 ms 3840 KB Output is correct
6 Correct 18 ms 5248 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 13304 KB Output is correct
2 Correct 71 ms 13148 KB Output is correct
3 Correct 48 ms 10488 KB Output is correct
4 Correct 12 ms 4224 KB Output is correct
5 Correct 10 ms 3840 KB Output is correct
6 Correct 18 ms 5248 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -