oj.uz

Submission #1113868

# Submission time Handle Problem Language Result Execution time Memory
1113868 2024-11-17T16:06:06 Z kiethm07 Dreaming (IOI13_dreaming) C++11
18 / 100
 33 ms 13384 KB 
#include <bits/stdc++.h>
#include "dreaming.h"

#define pii pair<int,int>
#define pli pair<long long,pii>
#define fi first
#define se second

#define vi vector<int>
#define vii vector<pii>
#define all(x) x.begin(),x.end()

using namespace std;

typedef long long ll;
typedef long double ld;

const int inf = 1e9;
const ll linf = 1e16;
const double pi = acos(-1);
const int maxN = 1e5 + 5;

vector<pii> a[maxN];
int down[maxN];
int up[maxN];

void dfsDown(int u,int p){
    down[u] = 0;
    for (int i = 0; i < a[u].size(); i++){
        int v,w;
        tie(v,w) = a[u][i];
        if (v == p) continue;
        dfsDown(v,u);
        down[u] = max(down[u], down[v] + w);
    }
}

void dfsUp(int u,int p,int& res){
    res = min(res, max(down[u], up[u]));
    int m1 = -1,m2 = -1;
    int i1 = -1,i2 = -1;
    for (int i = 0; i < a[u].size(); i++){
        int v = a[u][i].fi;
        int w = a[u][i].se;
        if (v == p) continue;
        if (down[v] + w > m2){
            m2 = down[v] + w;
            i2 = v;
        }
        if (m2 > m1){
            swap(m2,m1);
            swap(i2,i1);
        }
    }
    for (int i = 0; i < a[u].size(); i++){
        int v = a[u][i].fi;
        int w = a[u][i].se;
        if (v == p) continue;
        if (i1 == v && i2 == -1){
            up[v] = up[u] + w;
        }
        else{
            up[v] = max(up[u] + w,(v == i1 ? m2 : m1) + w);
        }
        dfsUp(v,u,res);
    }
}

int getVal(int u){
    dfsDown(u,-1);
    int res = inf;
    dfsUp(u,-1,res);
    return res;
}

int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    for (int i = 0; i < M; i++){
        int u = A[i] + 1;
        int v = B[i] + 1;
        int w = T[i];
        a[u].push_back(pii(v,w));
        a[v].push_back(pii(u,w));
    }
    vector<int> v;
    memset(down,-1,sizeof(down));
    for (int i = 1; i <= N; i++){
        if (down[i] != -1) continue;
        v.push_back(getVal(i));
    }
    sort(all(v),greater<int>());
    if (v.size() == 1) return v[0];
    if (v.size() == 2) return v[0] + v[1] + L;
    return max(v[0] + v[1] + L, v[1] + v[2] + L + L);
}

Compilation message

dreaming.cpp: In function 'void dfsDown(int, int)':
dreaming.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < a[u].size(); i++){
      |                     ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfsUp(int, int, int&)':
dreaming.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0; i < a[u].size(); i++){
      |                     ~~^~~~~~~~~~~~~
dreaming.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < a[u].size(); i++){
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 13384 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 14 ms 7380 KB Output is correct
2 Correct 14 ms 7344 KB Output is correct
3 Correct 14 ms 7380 KB Output is correct
4 Correct 14 ms 7376 KB Output is correct
5 Correct 13 ms 7376 KB Output is correct
6 Correct 15 ms 7636 KB Output is correct
7 Correct 14 ms 7504 KB Output is correct
8 Correct 13 ms 7300 KB Output is correct
9 Correct 15 ms 7372 KB Output is correct
10 Correct 16 ms 7504 KB Output is correct
11 Correct 2 ms 4432 KB Output is correct
12 Correct 4 ms 5068 KB Output is correct
13 Correct 4 ms 5068 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 4 ms 5236 KB Output is correct
16 Correct 4 ms 5068 KB Output is correct
17 Correct 4 ms 5068 KB Output is correct
18 Correct 4 ms 5068 KB Output is correct
19 Correct 4 ms 5176 KB Output is correct
20 Correct 1 ms 4748 KB Output is correct
21 Correct 2 ms 4432 KB Output is correct
22 Correct 2 ms 4432 KB Output is correct
23 Correct 4 ms 5068 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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