oj.uz

답안 #231494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
231494 2020-05-13T19:30:59 Z nickmet2004 꿈 (IOI13_dreaming) C++11
0 / 100
 63 ms 14968 KB 
#include<bits/stdc++.h>
#include"dreaming.h"
#define f first
#define s second

using namespace std;

const int N = 2e5 + 500;
typedef pair<int, int> ipair;
int n , m , L;
vector<ipair> adj[N];
int dpD[N] , dpU[N];
bool vis[N];
vector<int> dist;

int MN = 2e9 + 5;
int mx1 = -1 , mx2 = -1;

void dfsU(int u , int p , int BOSS){
    for(ipair x : adj[u]){
        int v = x.f , w = x.s;
        if(v == p) continue;
        if(u == BOSS){
            if(dpD[v] + w == mx1){
                if(mx2 == -1) dpU[v] = w;
                else dpU[v] = mx2 + w;
            } else dpU[v] = mx1 + w;
        }
        else dpU[v] = dpU[u] + w;
        dfsU(v , u , BOSS);
    }
    MN = min(MN , max(dpU[u] , dpD[u]));
}
void dfsD(int u , int BOSS){
    vis[u] = 1;
    for(ipair x : adj[u]){
        int v = x.f , w = x.s;
        if(vis[v]) continue;
        dfsD(v , BOSS);
        dpD[u] = max(dpD[u] , dpD[v] + w);
        if(u == BOSS){
            if(mx2 < dpD[v] + w){mx2 = dpD[v] + w; if(mx2 > mx1) swap(mx1 , mx2);}
        }
    }
    if(u == BOSS){ dfsU(u ,-1 , BOSS);}
}
int travelTime(int N , int M , int L , int A[] , int B[] , int C[]){
    n = N; m = M; L = L;
    for(int i = 0; i < m; ++i){
        adj[A[i]].emplace_back(B[i] , C[i]);
        adj[B[i]].emplace_back(A[i] , C[i]);
    }
    for(int i = 0; i < n; ++i){
        if(!vis[i]) {
            dfsD(i , i);
            dist.emplace_back(MN);
            //cerr << MN << " mn " << endl;
            MN = 2e9; mx1 = -1; mx2 = -1;
        }
    }
    sort(dist.begin() , dist.end()); reverse(dist.begin() ,dist.end());
    return max(dist[0] + dist[1] + L , dist[1] + dist[2] + L + L);
}
/*
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> L;
    for(int i = 0; i < m; ++i){
        int u , v , w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    for(int i = 0; i < n; ++i){
        if(!vis[i]) {
            dfsD(i , i);
            dist.emplace_back(MN);
            //cerr << MN << " mn " << endl;
            MN = 2e9; mx1 = -1; mx2 = -1;
        }
    }
    sort(dist.begin() , dist.end()); reverse(dist.begin() ,dist.end());
    cout << max(dist[0] + dist[1] + L , dist[1] + dist[2] + L + L);
}
*/

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 8960 KB Output is correct
2 Correct 31 ms 9128 KB Output is correct
3 Correct 32 ms 9004 KB Output is correct
4 Correct 32 ms 8952 KB Output is correct
5 Correct 30 ms 8960 KB Output is correct
6 Correct 30 ms 9472 KB Output is correct
7 Correct 32 ms 9216 KB Output is correct
8 Correct 29 ms 8952 KB Output is correct
9 Correct 35 ms 8956 KB Output is correct
10 Correct 30 ms 9076 KB Output is correct
11 Correct 7 ms 4992 KB Output is correct
12 Correct 11 ms 6396 KB Output is correct
13 Correct 11 ms 6524 KB Output is correct
14 Correct 10 ms 6396 KB Output is correct
15 Correct 10 ms 6396 KB Output is correct
16 Correct 10 ms 6268 KB Output is correct
17 Correct 10 ms 6012 KB Output is correct
18 Correct 11 ms 6524 KB Output is correct
19 Correct 10 ms 6396 KB Output is correct
20 Incorrect 7 ms 4992 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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