oj.uz

Submission #849289

# Submission time Handle Problem Language Result Execution time Memory
849289 2023-09-14T11:42:37 Z abcvuitunggio Dreaming (IOI13_dreaming) C++17
14 / 100
 114 ms 16540 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector <pair <int, int>> ke[100001];
int dp[100001],dp2[100001],ch[100001],mx;
priority_queue <int, vector <int>, greater <int>> q;
void dfs(int u, int p){
    ch[u]=1;
    for (auto [v,w]:ke[u])
        if (v!=p){
            dfs(v,u);
            dp[u]=max(dp[u],dp[v]+w);
        }
}
void dfs2(int u, int p){
    ch[u]=0;
    int mx=0,idx=-1,mx2=0;
    for (auto [v,w]:ke[u]){
        if (dp[v]+w>mx){
            mx2=mx;
            mx=dp[v]+w;
            idx=v;
        }
        else
            mx2=max(mx2,dp[v]+w);
    }
    for (auto [v,w]:ke[u]){
        dp2[v]=max(dp2[u],(v==idx?mx2:mx))+w;
        dfs2(v,u);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i=0;i<M;i++)
        ke[A[i]].emplace_back(B[i],T[i]);
    for (int i=0;i<N;i++)
        if (!ch[i])
            dfs(i,i);
    for (int i=0;i<N;i++)
        if (ch[i])
            dfs2(i,i);
    for (int i=0;i<N;i++){
        dp[i]=max(dp[i],dp2[i]);
    	mx=max(mx,dp[i]);
    }
    for (int i=0;i<M;i++){
        if (dp[A[i]]>dp[B[i]])
            ch[A[i]]=1;
        else
            ch[B[i]]=1;
    }
    for (int i=0;i<N;i++)
        if (!ch[i])
            q.push(dp[i]);
    while (q.size()>1){
        int x=q.top();
        q.pop();
        int y=q.top();
        q.pop();
        mx=max(mx,x+y+L);
        q.push(min(max(x,y+L),max(x+L,y)));
    }
    return mx;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 16520 KB Output is correct
2 Correct 91 ms 16540 KB Output is correct
3 Correct 54 ms 12368 KB Output is correct
4 Correct 8 ms 6492 KB Output is correct
5 Correct 10 ms 5772 KB Output is correct
6 Correct 18 ms 7288 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 35 ms 8540 KB Output is correct
9 Correct 50 ms 10440 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 84 ms 11736 KB Output is correct
12 Correct 114 ms 14216 KB Output is correct
13 Correct 1 ms 4956 KB Output is correct

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 Correct 74 ms 16520 KB Output is correct
2 Correct 91 ms 16540 KB Output is correct
3 Correct 54 ms 12368 KB Output is correct
4 Correct 8 ms 6492 KB Output is correct
5 Correct 10 ms 5772 KB Output is correct
6 Correct 18 ms 7288 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 35 ms 8540 KB Output is correct
9 Correct 50 ms 10440 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 84 ms 11736 KB Output is correct
12 Correct 114 ms 14216 KB Output is correct
13 Correct 1 ms 4956 KB Output is correct
14 Incorrect 1 ms 4956 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

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 Correct 74 ms 16520 KB Output is correct
2 Correct 91 ms 16540 KB Output is correct
3 Correct 54 ms 12368 KB Output is correct
4 Correct 8 ms 6492 KB Output is correct
5 Correct 10 ms 5772 KB Output is correct
6 Correct 18 ms 7288 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 35 ms 8540 KB Output is correct
9 Correct 50 ms 10440 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 84 ms 11736 KB Output is correct
12 Correct 114 ms 14216 KB Output is correct
13 Correct 1 ms 4956 KB Output is correct
14 Incorrect 1 ms 4956 KB Output isn't correct
15 Halted 0 ms 0 KB -