oj.uz

Submission #747588

# Submission time Handle Problem Language Result Execution time Memory
747588 2023-05-24T11:13:09 Z coding_snorlax Dreaming (IOI13_dreaming) C++14
0 / 100
 56 ms 15724 KB 
#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = int;
int dis1[200002] = {0};
ll dis2[200002] = {0};
vector<int> vis_node;
ll vis[200002] = {0};
ll Process[200002] = {0};
int cost;
void init(){
    for(int i:vis_node){
        vis[i]=0;
        dis2[i]=0;
        Process[i] = 1;
    }
    //vis_node.clear();
}
vector<pair<ll,ll>> G[100002];
void dfs_1(int node,int father,int weight){
    //cout << node << " ";
    vis_node.push_back(node);
    vis[node]=1;
    dis1[node] = dis1[father] + weight;
    for(auto i:G[node]){
        if(!vis[i.first]) dfs_1(i.first,node,i.second);
    }
}
void dfs_2(int node,int father,int weight){
    vis_node.push_back(node);
    vis[node]=1;
    dis2[node] = dis2[father] + weight;
    for(auto i:G[node]){
        if(!vis[i.first]) dfs_2(i.first,node,i.second);
    }
}
 int Node_f(int node){
    init();
    dfs_1(node,node,0);
    int Max = 0;
    int Max_place = 0;
    for(int i:vis_node){
        if(Max < dis1[i]){
            Max = dis1[i];
            Max_place = i;
        }
    }
    init();
    dfs_2(Max_place,Max_place,0);
    for(int i:vis_node){
        dis1[i] = dis2[i];
    }
    Max = 0; Max_place = 0;
    for(int i:vis_node){
        if(Max < dis1[i]){
            Max = dis1[i];
            Max_place = i;
        }
    }
    init();
    dfs_2(Max_place,Max_place,0);
    int answer = 1500000000;
    for(int i:vis_node){
        dis1[i] = max(dis1[i],dis2[i]);
        answer = min(dis1[i],answer);
    }
    //cout << endl;
 
    return answer;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    for(int i=0;i<M;i++){
        G[A[i]].push_back(make_pair(B[i],T[i]));
        G[B[i]].push_back(make_pair(A[i],T[i]));
    }
    cost = L;
    vector<int> List;
    for(int i=0;i<M;i++){
        if(!Process[i]){
            List.push_back(Node_f(i));
            //cout << i << " " << Node_f(i) << endl;
            //for(int j:vis_node) cout << j << " ";
            //cout << endl;
            vis_node.clear();
        }
    }
    sort(List.begin(),List.end());
    int answer = List.back();
    List.pop_back();
    return answer+List.back()+L;
}

Subtask #1
0 / 14.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7032 KB Output is correct
2 Incorrect 21 ms 7044 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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