oj.uz

Submission #575407

# Submission time Handle Problem Language Result Execution time Memory
575407 2022-06-10T10:34:23 Z ogibogi2004 Dreaming (IOI13_dreaming) C++14
18 / 100
 39 ms 12108 KB 
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
int sz=0;
bool vis[MAXN];
std::vector<std::pair<int,int> > g[MAXN];
int mpd[MAXN];// max path down
void dfs_init(int u,int par)
{
    mpd[u]=0;
    vis[u]=1;
    for(auto xd:g[u])
    {
        if(xd.first==par)continue;
        dfs_init(xd.first,u);
        mpd[u]=max(xd.second+mpd[xd.first],mpd[u]);
    }
}
int dfs_find(int u,int par,int len_up)
{
    int ret=max(mpd[u],len_up);
    int maxd=-1,ch=-1,che=-1;
    for(auto xd:g[u])
    {
        if(xd.first==par)continue;
        if(mpd[xd.first]>maxd)
        {
            maxd=mpd[xd.first];
            ch=xd.first;
            che=xd.second;
        }
    }
    if(ch==-1)
    {
        return ret;
    }
    len_up+=che;
    for(auto xd:g[u])
    {
        if(xd.first==par)continue;
        if(xd.first==ch)continue;
        len_up=max(len_up,mpd[xd.first]+che+xd.second);
    }
    return min(ret,dfs_find(ch,u,len_up));
}
void solve(int u)
{
    dfs_init(u,0);
    sz=dfs_find(u,0,0);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {

    for(int i=0;i<M;i++)
    {
        A[i]++;
        B[i]++;
        g[A[i]].push_back({B[i],T[i]});
        g[B[i]].push_back({A[i],T[i]});
    }
    vector<int>comps;
    for(int i=1;i<=N;i++)
    {
        if(vis[i]==0)
        {
            sz=0;
            solve(i);
            comps.push_back(sz);
        }
    }

    sort(comps.rbegin(),comps.rend());
    if(comps.size()==1)return comps[0];
    if(comps.size()==2)return comps[0]+comps[1]+L;
    return max(comps[0]+comps[1]+L,comps[1]+comps[2]+L+L);
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 12108 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 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 12108 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 17 ms 6256 KB Output is correct
2 Correct 20 ms 6260 KB Output is correct
3 Correct 20 ms 6232 KB Output is correct
4 Correct 18 ms 6228 KB Output is correct
5 Correct 25 ms 6188 KB Output is correct
6 Correct 23 ms 6736 KB Output is correct
7 Correct 19 ms 6308 KB Output is correct
8 Correct 28 ms 6180 KB Output is correct
9 Correct 21 ms 6124 KB Output is correct
10 Correct 26 ms 6356 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 6 ms 3812 KB Output is correct
13 Correct 5 ms 3792 KB Output is correct
14 Correct 4 ms 3808 KB Output is correct
15 Correct 5 ms 3816 KB Output is correct
16 Correct 6 ms 3708 KB Output is correct
17 Correct 4 ms 3664 KB Output is correct
18 Correct 4 ms 3792 KB Output is correct
19 Correct 5 ms 3792 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 5 ms 3792 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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