oj.uz

Submission #1078954

# Submission time Handle Problem Language Result Execution time Memory
1078954 2024-08-28T08:36:03 Z AndreasK Dreaming (IOI13_dreaming) C++17
14 / 100
 34 ms 18008 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

#define designed ios_base::sync_with_stdio(0);
#define by cin.tie(0);
#define AndreasK cout.tie(0);
//#define int long long
#define ii pair <int,int>
#define vi vector <int>
#define iii pair <int,ii>
#define vii vector <ii>
#define vc vector <char>
#define vb vector <bool>

vector <vii> g;
map <int,int> m;
vi v;
map <int,int> mn;

void dfs(int curr,int prev,int dist,int st){
v[curr]=st;
m[st]=max(m[st],dist);
for (auto nxt:g[curr]){
    if (nxt.first!=prev)
        dfs(nxt.first,curr,nxt.second+dist,st);
}
}

void dfs2(int curr,int prev,int dist,int st){
v[curr]=st;
mn[st]=min(mn[st],max(m[st]-dist,dist));
for (auto nxt:g[curr]){
    if (nxt.first!=prev)
        dfs2(nxt.first,curr,nxt.second+dist,st);
}
}

int travelTime(int N,int M,int L,int A[],int B[],int T[]){
g.assign(N,vii());
for (int c=0;c<M;c++){
    g[A[c]].push_back({B[c],T[c]});
    g[B[c]].push_back({A[c],T[c]});
}
m.clear();
int st=0;
v.assign(N,0);
for (int c=0;c<N;c++){
    if (v[c]==0 && g[c].size()==1){
        st++;
        dfs(c,c,0,st);
    }
}
mn.clear();
mn[1]=m[1];
mn[2]=m[2];
st=0;
v.assign(N,0);
for (int c=0;c<N;c++){
    if (v[c]==0 && g[c].size()==1){
        st++;
        dfs2(c,c,0,st);
    }
}
return max({m[1],m[2],mn[1]+mn[2]+L});
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18008 KB Output is correct
2 Correct 31 ms 17852 KB Output is correct
3 Correct 21 ms 12112 KB Output is correct
4 Correct 5 ms 2904 KB Output is correct
5 Correct 4 ms 1596 KB Output is correct
6 Correct 9 ms 4188 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 16 ms 6320 KB Output is correct
9 Correct 21 ms 9048 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 28 ms 11580 KB Output is correct
12 Correct 34 ms 14676 KB Output is correct
13 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18008 KB Output is correct
2 Correct 31 ms 17852 KB Output is correct
3 Correct 21 ms 12112 KB Output is correct
4 Correct 5 ms 2904 KB Output is correct
5 Correct 4 ms 1596 KB Output is correct
6 Correct 9 ms 4188 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 16 ms 6320 KB Output is correct
9 Correct 21 ms 9048 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 28 ms 11580 KB Output is correct
12 Correct 34 ms 14676 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18008 KB Output is correct
2 Correct 31 ms 17852 KB Output is correct
3 Correct 21 ms 12112 KB Output is correct
4 Correct 5 ms 2904 KB Output is correct
5 Correct 4 ms 1596 KB Output is correct
6 Correct 9 ms 4188 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 16 ms 6320 KB Output is correct
9 Correct 21 ms 9048 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 28 ms 11580 KB Output is correct
12 Correct 34 ms 14676 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -