oj.uz

Submission #468036

# Submission time Handle Problem Language Result Execution time Memory
468036 2021-08-26T04:47:45 Z SirCovidThe19th Dreaming (IOI13_dreaming) C++17
18 / 100
 54 ms 12708 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std; 

#define pii pair<int, int>
#define f first
#define s second

const int mx = 1e5 + 5, inf = 1e9;

vector<pair<int, int>> adj[mx]; pii in[mx]; bool vis[mx];

void comb(pii &p, int x){
	if (x > p.f) p.s = p.f, p.f = x;
	else if (x > p.s) p.s = x;
}
void dfs1(int i, int p){
    vis[i] = 1;
    for (auto [x, w] : adj[i]) if (x != p){
        dfs1(x, i); 
		comb(in[i], in[x].f + w);
    }
}
void dfs2(int i, int p, int pout, int &mnD){
    mnD = min(mnD, max(pout, in[i].f));
    for (auto [x, w] : adj[i]) if (x != p){
        int sib = (in[i].f == in[x].f + w) ? in[i].s : in[i].f;
        int out = max(sib + w, pout);
        dfs2(x, i, out, mnD);
    }
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]){
    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]});
    }
    int w[3] = {-l, -l, -l};
    for (int i = 1; i <= n; i++) if (!vis[i]){
        int mnD = 1e9; dfs1(i, 0); dfs2(i, 0, 0, mnD);
		if (mnD > w[0]) w[2] = w[1], w[1] = w[0], w[0] = mnD;
		else if (mnD > w[1]) w[2] = w[1], w[1] = mnD;
		else if (mnD > w[2]) w[2] = mnD;
    }
	return max(w[0] + w[1] + l, w[1] + w[2] + 2 * l);
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 12708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 12708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5848 KB Output is correct
2 Correct 21 ms 6260 KB Output is correct
3 Correct 33 ms 6140 KB Output is correct
4 Correct 22 ms 6220 KB Output is correct
5 Correct 23 ms 6156 KB Output is correct
6 Correct 34 ms 6428 KB Output is correct
7 Correct 21 ms 6348 KB Output is correct
8 Correct 21 ms 6124 KB Output is correct
9 Correct 20 ms 6100 KB Output is correct
10 Correct 25 ms 6348 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 4 ms 3276 KB Output is correct
13 Correct 4 ms 3412 KB Output is correct
14 Correct 4 ms 3276 KB Output is correct
15 Correct 4 ms 3292 KB Output is correct
16 Correct 3 ms 3164 KB Output is correct
17 Correct 5 ms 2784 KB Output is correct
18 Correct 4 ms 3404 KB Output is correct
19 Correct 3 ms 3148 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2656 KB Output is correct
22 Correct 2 ms 2636 KB Output is correct
23 Correct 4 ms 3148 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 12708 KB Output isn't correct
2 Halted 0 ms 0 KB -