oj.uz

답안 #819995

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
819995 2023-08-10T17:18:25 Z annabeth9680 꿈 (IOI13_dreaming) C++17
0 / 100
 40 ms 13624 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int MAXN = 1e5+5;
vector<pair<int,int>> adj[MAXN];
bool visited[MAXN], visited2[MAXN];
pair<int,int> dijkstra(bool *vis, int src){
    int maxn = -1, pos = -1;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,src}); vis[src] = true;
    while(!pq.empty()){
        int u = pq.top().second, cdist = pq.top().first; pq.pop();
        for(auto p : adj[u]){ //first node, then weight
            if(!vis[p.first]){
                vis[p.first] = true;
                pq.push({cdist+p.second,p.first});
                if(cdist+p.second > maxn){
                    maxn = cdist+p.second;
                    pos = p.first;
                }
            }
        }
    }
    return {maxn,pos};
}
int res,laenge;
bool calc(int u, int b, int p, int d){
    if(u == b) return true;
    for(auto v : adj[u]){
        if(v.first != p){
            if(calc(v.first,b,u,d+v.second)){
                res = min(res,max(d,laenge-d));
                return true;
            }
        }
    }
    return false;
}
int get_dia(int x){
    int a = dijkstra(visited2,x).second;
    pair<int,int> ret = dijkstra(visited,a); //first is the longest path, second the second node on the longest path
    res = ret.first; laenge = ret.first;
    calc(a,ret.second,-1,0); //find the smallest value on the path
    //cout << x << " " << res << "\n";
    return res;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    memset(visited,false,sizeof(visited));
    for(int i = 0;i<M;++i){
        adj[A[i]].push_back({B[i],T[i]});
        adj[B[i]].push_back({A[i],T[i]});
    }
    int ans = 0;
    for(int i = 0;i<N;++i){
        if(!visited[i]){
            int a = dijkstra(visited2,i).second;
            pair<int,int> ret = dijkstra(visited,a); //first is the longest path, second the second node on the longest path
            ans = max(ans,ret.second);
        }
    }
    memset(visited,false,sizeof(visited)); memset(visited2,false,sizeof(visited2));
    vector<int> dias;
    for(int i = 0;i<N;++i){
        if(!visited[i]){
            dias.push_back(get_dia(i));
        }
    }
    sort(dias.rbegin(),dias.rend());
    if(dias.size() > 1){
        ans = max(ans,dias[0]+dias[1]+L);
    }
    if(dias.size() > 2){
        ans = max(ans,dias[1]+dias[2]+2*L);
    }
    return ans;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 40 ms 13624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 40 ms 13624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 5968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 40 ms 13624 KB Output isn't correct
2 Halted 0 ms 0 KB -