oj.uz

Submission #900570

# Submission time Handle Problem Language Result Execution time Memory
900570 2024-01-08T14:42:24 Z JakobZorz Dreaming (IOI13_dreaming) C++17
18 / 100
 185 ms 32452 KB 
#include"dreaming.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;

vector<pair<ll,ll>>nodes[100000];
bool vis[100000];
vector<ll>node_list;

void dfs(ll node){
    if(vis[node])
        return;
    vis[node]=true;
    node_list.push_back(node);
    for(auto ne:nodes[node])
        dfs(ne.first);
}

map<pair<ll,ll>,ll>dp;
ll get_max_dist(ll node,ll prev){
    if(dp.count({node,prev}))
        return dp[{node,prev}];
    
    ll res=0;
    for(auto ne:nodes[node]){
        if(ne.first==prev)
            continue;
        res=max(res,get_max_dist(ne.first,node)+ne.second);
    }
    dp[{node,prev}]=res;
    return res;
}

ll get_diameter(ll root){
    node_list.clear();
    dfs(root);
    /*cout<<"- ";
    for(int i:node_list)
        cout<<i<<" ";
    cout<<"\n";*/
    
    ll res=1e18;
    for(ll node:node_list){
        //cout<<node<<": "<<get_max_dist(node,node)<<"\n";
        res=min(res,get_max_dist(node,node));
    }
    return res;
}

int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    for(ll i=0;i<M;i++){
        nodes[A[i]].emplace_back(B[i],T[i]);
        nodes[B[i]].emplace_back(A[i],T[i]);
    }
    
    vector<ll>dists;
    for(ll i=0;i<N;i++)
        if(!vis[i])
            dists.push_back(get_diameter(i));
    
    sort(dists.begin(),dists.end());
    reverse(dists.begin(),dists.end());
    if(dists.size()==1)
        return dists[0];
    else if(dists.size()==2)
        return dists[0]+dists[1]+L;
    else
        return max(dists[0]+dists[1]+L,dists[1]+dists[2]+2*L);
}

Subtask #1
0 / 14.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 32452 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 64 ms 16068 KB Output is correct
2 Correct 59 ms 16072 KB Output is correct
3 Correct 78 ms 16072 KB Output is correct
4 Correct 54 ms 16076 KB Output is correct
5 Correct 56 ms 16072 KB Output is correct
6 Correct 68 ms 17592 KB Output is correct
7 Correct 68 ms 16588 KB Output is correct
8 Correct 54 ms 15828 KB Output is correct
9 Correct 54 ms 15696 KB Output is correct
10 Correct 63 ms 16584 KB Output is correct
11 Correct 1 ms 3832 KB Output is correct
12 Correct 19 ms 10960 KB Output is correct
13 Correct 18 ms 10908 KB Output is correct
14 Correct 17 ms 10776 KB Output is correct
15 Correct 18 ms 10952 KB Output is correct
16 Correct 17 ms 10956 KB Output is correct
17 Correct 21 ms 10704 KB Output is correct
18 Correct 19 ms 10960 KB Output is correct
19 Correct 17 ms 10748 KB Output is correct
20 Correct 1 ms 3928 KB Output is correct
21 Correct 1 ms 3676 KB Output is correct
22 Correct 1 ms 3928 KB Output is correct
23 Correct 18 ms 10860 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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