oj.uz

Submission #1043783

# Submission time Handle Problem Language Result Execution time Memory
1043783 2024-08-04T17:13:29 Z vanea Dreaming (IOI13_dreaming) C++14
0 / 100
 25 ms 12380 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
using ld = long double;

const int mxN = 1e5+10;

vector<array<int, 2>> adj[mxN];
bool vis[mxN];
ll ans = 0, mx1 = 0, mx2 = 0, mx_1[mxN], mx_2[mxN];

ll dfs(int node, int p) {
    ll mx1 = 0, mx2 = 0;
    vis[node] = true;
    for(auto [it, w] : adj[node]) {
        if(it == p) continue;
        mx2 = max(mx2, dfs(it, node)+w);
        if(mx2 > mx1) swap(mx1, mx2);
    }
    ans = max(ans, mx2+mx1);
    mx_1[node] = mx1;
    mx_2[node] = mx2;
    return mx1;
}

ll dfs1(int node, int p) {
    ll mn = mx_1[node];
    vis[node] = true;
    for(auto [it, w] : adj[node]) {
        if(it == p) continue;
        if(mx_1[node]-w == mx_1[it]) {
            mx_2[it] = max(mx_2[it], mx_2[node]+w);
            if(mx_2[it] > mx_1[it]) swap(mx_2[it], mx_1[it]);
        }
        else {
            int init = mx_1[it];
            mx_2[it] = max(mx_2[it], mx_1[node]+w);
            if(mx_2[it] > mx_1[it]) swap(mx_2[it], mx_1[it]);
            if(mx_2[node]-w != init) {
                mx_2[it] = max(mx_2[it], mx_2[node]+w);
            }
        }
        mn = min(mn, mx_1[it]);
        dfs1(it, node);
    }
    return mn;
}

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]});
    }
    for(int i = 0; i < n; i++) {
        if(!vis[i]) dfs(i, -1);
    }
    if(m == n-1) return ans;
    memset(vis, false, sizeof vis);
    for(int i = 0; i < n; i++) {
        if(!vis[i]) {
            mx2 = max(mx2, dfs1(i, -1));
            if(mx2 > mx1) swap(mx1, mx2);
        }
    }
    return max(ans, mx1+mx2+l);
}
/*
int main()
{
    int a[8] = {0,8,2,5,5,1,1,10};
    int b[8] = {8,2,7,11,1,3,9,6};
    int c[8] = {4,2,4,3,7,1,5,3};
    cout << travelTime(12, 8, 2, a, b, c);
}*/

Compilation message

dreaming.cpp: In function 'll dfs(int, int)':
dreaming.cpp:16:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |     for(auto [it, w] : adj[node]) {
      |              ^
dreaming.cpp: In function 'll dfs1(int, int)':
dreaming.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto [it, w] : adj[node]) {
      |              ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12380 KB Output is correct
2 Correct 25 ms 12048 KB Output is correct
3 Correct 17 ms 11356 KB Output is correct
4 Correct 4 ms 6232 KB Output is correct
5 Correct 3 ms 5980 KB Output is correct
6 Correct 7 ms 7004 KB Output is correct
7 Incorrect 1 ms 5212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5212 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Incorrect 1 ms 5212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12380 KB Output is correct
2 Correct 25 ms 12048 KB Output is correct
3 Correct 17 ms 11356 KB Output is correct
4 Correct 4 ms 6232 KB Output is correct
5 Correct 3 ms 5980 KB Output is correct
6 Correct 7 ms 7004 KB Output is correct
7 Incorrect 1 ms 5212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7512 KB Output is correct
2 Incorrect 9 ms 7536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5212 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Incorrect 1 ms 5212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12380 KB Output is correct
2 Correct 25 ms 12048 KB Output is correct
3 Correct 17 ms 11356 KB Output is correct
4 Correct 4 ms 6232 KB Output is correct
5 Correct 3 ms 5980 KB Output is correct
6 Correct 7 ms 7004 KB Output is correct
7 Incorrect 1 ms 5212 KB Output isn't correct
8 Halted 0 ms 0 KB -