oj.uz

Submission #967780

# Submission time Handle Problem Language Result Execution time Memory
967780 2024-04-22T19:53:31 Z Hugo1729 Dreaming (IOI13_dreaming) C++17
18 / 100
 25 ms 11856 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define f first
#define s second

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

pair<int,pair<int,int>> dp[100000];
bool marked[100000]={0};

int dfs_sizes(int v, int pV){
    dp[v]={-1,{0,0}};
    marked[v]=1;
    for(auto [w,d] : adj[v]){
        if(w!=pV){
            int sus=dfs_sizes(w,v)+d;
            if(sus>dp[v].s.f)dp[v]={w,{sus,dp[v].s.f}};
            else if(sus>dp[v].s.s)dp[v].s.s=sus;
        }
    }
    // cout << v << ' ' << dp[v].f << ' ' << dp[v].s.f <<' ' << dp[v].s.s << '\n';

    return dp[v].s.f;
}

int dfs(int v, int pV=-1, int d=0){
    // cout << "d" << v << ' ' << d << '\n';
    if(dp[v].f!=-1){
        int sus=max(dp[dp[v].f].s.s,d+dp[v].s.f-dp[dp[v].f].s.f+dp[v].s.s);
        if(max(sus,dp[dp[v].f].s.f)<max(d,dp[v].s.f))return dfs(dp[v].f,v,sus);
        else return max(d,dp[v].s.f);
    }
    return max(d,dp[v].s.f);
}


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]});
    }

    vector<int> sussy;

    for(int i=0;i<N;i++){
        if(!marked[i]){
            dfs_sizes(i,i);
            sussy.push_back(-dfs(i));
            // cout <<i << ' ' << sussy[sussy.size()-1] << '\n';
        }

        // cout << i << ' ' << dp[i].first << ' ' << dp[i].second << '\n';

    }

    sort(sussy.begin(),sussy.end());

    if(sussy.size()==1)return -sussy[0];
    else if(sussy.size()==2)return -sussy[0]-sussy[1]+L;

    return max(-sussy[0]-sussy[1]+L,-sussy[2]-sussy[1]+L*2);
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 11856 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 12 ms 7516 KB Output is correct
2 Correct 15 ms 7512 KB Output is correct
3 Correct 12 ms 7516 KB Output is correct
4 Correct 12 ms 7516 KB Output is correct
5 Correct 12 ms 7516 KB Output is correct
6 Correct 13 ms 7900 KB Output is correct
7 Correct 14 ms 7516 KB Output is correct
8 Correct 12 ms 7392 KB Output is correct
9 Correct 12 ms 7384 KB Output is correct
10 Correct 13 ms 7568 KB Output is correct
11 Correct 1 ms 4956 KB Output is correct
12 Correct 3 ms 5592 KB Output is correct
13 Correct 3 ms 5592 KB Output is correct
14 Correct 3 ms 5592 KB Output is correct
15 Correct 3 ms 5592 KB Output is correct
16 Correct 3 ms 5592 KB Output is correct
17 Correct 3 ms 5592 KB Output is correct
18 Correct 3 ms 5588 KB Output is correct
19 Correct 3 ms 5592 KB Output is correct
20 Correct 1 ms 2908 KB Output is correct
21 Correct 1 ms 2908 KB Output is correct
22 Correct 1 ms 5036 KB Output is correct
23 Correct 3 ms 5592 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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