oj.uz

Submission #208000

# Submission time Handle Problem Language Result Execution time Memory
208000 2020-03-09T17:32:37 Z Andrei_Cotor Dreaming (IOI13_dreaming) C++11
32 / 100
 73 ms 12536 KB 
#include<dreaming.h>
#include<vector>
#include<algorithm>

using namespace std;

vector<pair<int,int> > V[100005];
int DistMax[100005],Dist[100005],R[100005],Viz[100005];

int dfs(int nod, int cc)
{
    Viz[nod]=cc;
    int mx1=0,mx2=0;
    int rez=0;

    for(auto other:V[nod])
    {
        if(Viz[other.first])
            continue;

        rez=max(rez,dfs(other.first,cc));

        int val=DistMax[other.first]+other.second;
        if(val>=mx1)
        {
            mx2=mx1;
            mx1=val;
        }
        else if(val>mx2)
            mx2=val;
    }

    DistMax[nod]=mx1;
    rez=max(rez,mx1+mx2);
    return rez;
}

int distmin(int nod, int p, int dist)
{
    int rez=max(dist,DistMax[nod]);

    int mx1=0,mx2=0;
    for(auto other:V[nod])
    {
        if(other.first==p)
            continue;

        int val=DistMax[other.first]+other.second;
        if(val>=mx1)
        {
            mx2=mx1;
            mx1=val;
        }
        else if(val>mx2)
            mx2=val;
    }

    for(auto other:V[nod])
    {
        if(other.first==p)
            continue;

        int val=DistMax[other.first]+other.second;
        if(val!=mx1)
            rez=min(rez,distmin(other.first,nod,dist+other.second+mx1));
        else
            rez=min(rez,distmin(other.first,nod,dist+other.second+mx2));
    }
    return rez;
}

int travelTime(int n, int M, int L, int A[], int B[], int T[])
{
    for(int i=0; i<M; i++)
    {
        V[A[i]+1].push_back({B[i]+1,T[i]});
        V[B[i]+1].push_back({A[i]+1,T[i]});
    }

    int nrc=0;
    int rez=0;
    for(int i=1; i<=n; i++)
    {
        if(!Viz[i])
        {
            nrc++;
            rez=max(rez,dfs(i,nrc));
            R[nrc]=i;
        }
    }

    for(int i=1; i<=nrc; i++)
        Dist[i]=distmin(R[i],0,0);

    sort(Dist+1,Dist+nrc+1);

    if(nrc>=2)
        rez=max(rez,Dist[nrc]+Dist[nrc-1]+L);
    if(nrc>=3)
        rez=max(rez,Dist[nrc-1]+Dist[nrc-2]+2*L);

    return rez;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 12536 KB Output is correct
2 Correct 66 ms 12280 KB Output is correct
3 Correct 43 ms 10744 KB Output is correct
4 Correct 13 ms 4088 KB Output is correct
5 Correct 12 ms 3576 KB Output is correct
6 Correct 19 ms 4856 KB Output is correct
7 Correct 6 ms 2680 KB Output is correct
8 Correct 31 ms 6776 KB Output is correct
9 Correct 40 ms 8952 KB Output is correct
10 Correct 6 ms 2808 KB Output is correct
11 Correct 67 ms 10008 KB Output is correct
12 Correct 73 ms 11176 KB Output is correct
13 Correct 6 ms 2712 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 12536 KB Output is correct
2 Correct 66 ms 12280 KB Output is correct
3 Correct 43 ms 10744 KB Output is correct
4 Correct 13 ms 4088 KB Output is correct
5 Correct 12 ms 3576 KB Output is correct
6 Correct 19 ms 4856 KB Output is correct
7 Correct 6 ms 2680 KB Output is correct
8 Correct 31 ms 6776 KB Output is correct
9 Correct 40 ms 8952 KB Output is correct
10 Correct 6 ms 2808 KB Output is correct
11 Correct 67 ms 10008 KB Output is correct
12 Correct 73 ms 11176 KB Output is correct
13 Correct 6 ms 2712 KB Output is correct
14 Correct 6 ms 2680 KB Output is correct
15 Correct 6 ms 2680 KB Output is correct
16 Incorrect 6 ms 2680 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 12536 KB Output is correct
2 Correct 66 ms 12280 KB Output is correct
3 Correct 43 ms 10744 KB Output is correct
4 Correct 13 ms 4088 KB Output is correct
5 Correct 12 ms 3576 KB Output is correct
6 Correct 19 ms 4856 KB Output is correct
7 Correct 6 ms 2680 KB Output is correct
8 Correct 31 ms 6776 KB Output is correct
9 Correct 40 ms 8952 KB Output is correct
10 Correct 6 ms 2808 KB Output is correct
11 Correct 67 ms 10008 KB Output is correct
12 Correct 73 ms 11176 KB Output is correct
13 Correct 6 ms 2712 KB Output is correct
14 Correct 6 ms 2680 KB Output is correct
15 Correct 6 ms 2680 KB Output is correct
16 Incorrect 6 ms 2680 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6648 KB Output is correct
2 Correct 35 ms 6776 KB Output is correct
3 Correct 29 ms 6648 KB Output is correct
4 Correct 30 ms 6648 KB Output is correct
5 Correct 28 ms 6648 KB Output is correct
6 Correct 30 ms 6904 KB Output is correct
7 Correct 30 ms 6780 KB Output is correct
8 Correct 29 ms 6520 KB Output is correct
9 Correct 46 ms 6520 KB Output is correct
10 Correct 30 ms 6904 KB Output is correct
11 Correct 6 ms 2680 KB Output is correct
12 Correct 9 ms 4216 KB Output is correct
13 Correct 9 ms 4216 KB Output is correct
14 Correct 9 ms 4216 KB Output is correct
15 Correct 9 ms 4216 KB Output is correct
16 Correct 9 ms 4344 KB Output is correct
17 Correct 9 ms 4216 KB Output is correct
18 Correct 9 ms 4216 KB Output is correct
19 Correct 9 ms 4216 KB Output is correct
20 Correct 6 ms 2680 KB Output is correct
21 Correct 6 ms 2680 KB Output is correct
22 Correct 6 ms 2680 KB Output is correct
23 Correct 9 ms 4216 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 12536 KB Output is correct
2 Correct 66 ms 12280 KB Output is correct
3 Correct 43 ms 10744 KB Output is correct
4 Correct 13 ms 4088 KB Output is correct
5 Correct 12 ms 3576 KB Output is correct
6 Correct 19 ms 4856 KB Output is correct
7 Correct 6 ms 2680 KB Output is correct
8 Correct 31 ms 6776 KB Output is correct
9 Correct 40 ms 8952 KB Output is correct
10 Correct 6 ms 2808 KB Output is correct
11 Correct 67 ms 10008 KB Output is correct
12 Correct 73 ms 11176 KB Output is correct
13 Correct 6 ms 2712 KB Output is correct
14 Correct 6 ms 2680 KB Output is correct
15 Correct 7 ms 2808 KB Output is correct
16 Correct 7 ms 2808 KB Output is correct
17 Correct 6 ms 2680 KB Output is correct
18 Correct 7 ms 2808 KB Output is correct
19 Correct 7 ms 2808 KB Output is correct
20 Correct 7 ms 2808 KB Output is correct
21 Correct 7 ms 2808 KB Output is correct
22 Correct 8 ms 2936 KB Output is correct
23 Correct 6 ms 2680 KB Output is correct
24 Correct 6 ms 2680 KB Output is correct
25 Correct 6 ms 2680 KB Output is correct
26 Incorrect 7 ms 2680 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 12536 KB Output is correct
2 Correct 66 ms 12280 KB Output is correct
3 Correct 43 ms 10744 KB Output is correct
4 Correct 13 ms 4088 KB Output is correct
5 Correct 12 ms 3576 KB Output is correct
6 Correct 19 ms 4856 KB Output is correct
7 Correct 6 ms 2680 KB Output is correct
8 Correct 31 ms 6776 KB Output is correct
9 Correct 40 ms 8952 KB Output is correct
10 Correct 6 ms 2808 KB Output is correct
11 Correct 67 ms 10008 KB Output is correct
12 Correct 73 ms 11176 KB Output is correct
13 Correct 6 ms 2712 KB Output is correct
14 Correct 6 ms 2680 KB Output is correct
15 Correct 6 ms 2680 KB Output is correct
16 Incorrect 6 ms 2680 KB Output isn't correct
17 Halted 0 ms 0 KB -