oj.uz

Submission #344122

# Submission time Handle Problem Language Result Execution time Memory
344122 2021-01-05T07:27:02 Z katearima Dreaming (IOI13_dreaming) C++14
18 / 100
 54 ms 12908 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
const int R=1e5+5;
vector<pair<int,int>> adj[R];
int dpD1[R], dpD2[R], dpU[R], mn;
vector<bool> visited(R);
vector<int> ans;
void dfsDown(int k){
    visited[k]=true;
    for(auto u:adj[k]){
        int dist=u.ss; int ch=u.ff;
        if(visited[ch]) continue;
        dfsDown(ch);
        if(dpD1[ch]+dist > dpD1[k]){
            dpD2[k]=dpD1[k];
            dpD1[k]=dpD1[ch]+dist;
        }
        else if(dpD1[ch]+dist > dpD2[k]){
            dpD2[k]=dpD1[ch]+dist;
        }
    }

}
void dfsUp(int k, int par){
    for(auto u:adj[k]){
        int dist=u.ss; int ch=u.ff;
        if(ch==par) continue;
        dpU[ch]=dpU[k]+dist;
        if(dpD1[k]==dpD1[ch]+dist) dpU[ch]=max(dpU[ch], dpD2[k]+dist);
        else dpU[ch]=max(dpU[ch], dpD1[k]+dist);
        //cout<<"child: " << ch << "parent: "<< k<<  "UP" << dpU[ch]<<endl;
        dfsUp(ch, k);
    }
    mn=min(mn, max(dpD1[k], dpU[k]));
}
int travelTime(int n, int m, int l, int a[], int b[], int time[]) {
    for(int i=0; i<m; i++){
        adj[a[i]].push_back(make_pair(b[i], time[i]));
        adj[b[i]].push_back(make_pair(a[i], time[i]));
    }
    for(int i=0; i<n; i++){
        if(visited[i]) continue;
        mn=INT_MAX;
        dfsDown(i);
        dfsUp(i, -1);
        //cout<<mn<<endl;
        ans.push_back(mn);

    }

    sort(ans.begin(), ans.end());
    reverse(ans.begin(), ans.end());
    if(ans.size()>2) return max(ans[1]+ans[2]+2*l, ans[0]+ans[1]+l);
    else if(ans.size()>1) return ans[0]+ans[1]+l;
    else return ans[0];
    return 42;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 12908 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 25 ms 6892 KB Output is correct
2 Correct 27 ms 6888 KB Output is correct
3 Correct 26 ms 6896 KB Output is correct
4 Correct 24 ms 6892 KB Output is correct
5 Correct 24 ms 6892 KB Output is correct
6 Correct 27 ms 7408 KB Output is correct
7 Correct 27 ms 7152 KB Output is correct
8 Correct 25 ms 6896 KB Output is correct
9 Correct 28 ms 6764 KB Output is correct
10 Correct 27 ms 7036 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 6 ms 4200 KB Output is correct
13 Correct 6 ms 4324 KB Output is correct
14 Correct 6 ms 4200 KB Output is correct
15 Correct 6 ms 4200 KB Output is correct
16 Correct 6 ms 4196 KB Output is correct
17 Correct 6 ms 3688 KB Output is correct
18 Correct 7 ms 4472 KB Output is correct
19 Correct 6 ms 4200 KB Output is correct
20 Correct 2 ms 2668 KB Output is correct
21 Correct 2 ms 2668 KB Output is correct
22 Correct 2 ms 2796 KB Output is correct
23 Correct 7 ms 4072 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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