oj.uz

Submission #842939

# Submission time Handle Problem Language Result Execution time Memory
842939 2023-09-03T13:40:46 Z 12345678 Dreaming (IOI13_dreaming) C++17
18 / 100
 46 ms 19312 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;
int mx[nx], mxr[nx], nxt=0, mx1=INT_MAX, mx2=INT_MAX, ans, cmx, cnt;
bool vs[nx];
vector<vector<pair<int, int>>> d(nx);
vector<int> b(nx), c;

void dfs(int u, int p)
{
    vs[u]=1; c.push_back(u);
    for (auto [v, w]:d[u])
    {
        if (v==p) continue;
        dfs(v, u);
        mx[u]=max(mx[u], mx[v]+w);
    }
}

void dfs2(int u, int p)
{
    vector<int> pf(d[u].size()+2), sf(d[u].size()+2);
    pf[0]=mxr[u];
    for (int i=d[u].size()-1; i>=0; i--)
    {
        sf[i+1]=sf[i+2];
        if (d[u][i].first==p) continue;
        sf[i+1]=max(sf[i+1], d[u][i].second+mx[d[u][i].first]);
    }
    for (int i=0; i<d[u].size(); i++)
    {
        pf[i+1]=pf[i];
        if (d[u][i].first==p) continue;
        pf[i+1]=max(pf[i+1], d[u][i].second+mx[d[u][i].first]);
        mxr[d[u][i].first]=max(pf[i], sf[i+2])+d[u][i].second;
    }
    for (auto [v, w]:d[u]) if (v!=p) dfs2(v, u);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    if (N==1) return 0;
    if (N==2&&M==1) return T[0];
    if (N==2) return L;
    for (int i=0; i<M; i++) d[A[i]].push_back({B[i], T[i]}), d[B[i]].push_back({A[i], T[i]});
    for (int i=0; i<N; i++)
    {
        if (vs[i]) continue;
        c.clear();
        dfs(i, i); dfs2(i, i);
        cmx=INT_MAX;
        for (auto x:c) cmx=min(cmx, max(mx[x], mxr[x]));
        b[cnt++]=cmx;
    }
    for (int i=0; i<N; i++) ans=max(ans, mx[i]+mxr[i]);
    sort(b.begin(), b.end());
    reverse(b.begin(), b.end());
    return max(ans, max(b[0]+L+b[1], b[1]+2*L+b[2]));
}

Compilation message

dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i=0; i<d[u].size(); i++)
      |                   ~^~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19312 KB Output is correct
2 Correct 44 ms 18484 KB Output is correct
3 Correct 35 ms 17584 KB Output is correct
4 Correct 8 ms 5468 KB Output is correct
5 Correct 8 ms 4188 KB Output is correct
6 Correct 12 ms 6600 KB Output is correct
7 Incorrect 3 ms 3164 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19312 KB Output is correct
2 Correct 44 ms 18484 KB Output is correct
3 Correct 35 ms 17584 KB Output is correct
4 Correct 8 ms 5468 KB Output is correct
5 Correct 8 ms 4188 KB Output is correct
6 Correct 12 ms 6600 KB Output is correct
7 Incorrect 3 ms 3164 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6248 KB Output is correct
2 Correct 18 ms 6236 KB Output is correct
3 Correct 18 ms 6340 KB Output is correct
4 Correct 22 ms 6236 KB Output is correct
5 Correct 20 ms 6140 KB Output is correct
6 Correct 19 ms 6492 KB Output is correct
7 Correct 20 ms 6500 KB Output is correct
8 Correct 18 ms 6108 KB Output is correct
9 Correct 19 ms 6236 KB Output is correct
10 Correct 17 ms 6236 KB Output is correct
11 Correct 3 ms 3164 KB Output is correct
12 Correct 7 ms 3996 KB Output is correct
13 Correct 7 ms 3932 KB Output is correct
14 Correct 7 ms 3816 KB Output is correct
15 Correct 7 ms 3932 KB Output is correct
16 Correct 7 ms 3676 KB Output is correct
17 Correct 9 ms 3420 KB Output is correct
18 Correct 7 ms 3932 KB Output is correct
19 Correct 7 ms 3676 KB Output is correct
20 Correct 2 ms 3164 KB Output is correct
21 Correct 1 ms 3164 KB Output is correct
22 Correct 3 ms 3232 KB Output is correct
23 Correct 7 ms 3676 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19312 KB Output is correct
2 Correct 44 ms 18484 KB Output is correct
3 Correct 35 ms 17584 KB Output is correct
4 Correct 8 ms 5468 KB Output is correct
5 Correct 8 ms 4188 KB Output is correct
6 Correct 12 ms 6600 KB Output is correct
7 Incorrect 3 ms 3164 KB Output isn't correct
8 Halted 0 ms 0 KB -