oj.uz

답안 #893082

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893082 2023-12-26T13:30:25 Z raul2008487 꿈 (IOI13_dreaming) C++17
18 / 100
 61 ms 15304 KB 
#include<bits/stdc++.h>
#include "dreaming.h"
#define ll long long
#define pll pair<ll,ll>
#define vl vector<ll>
#define fi first
#define se second
#define in insert
#define all(v) v.begin(),v.end()
const int sz = 100005;
const ll inf = 1000000000000000;
using namespace std;
vector<pair<ll,ll>> adj[sz];
ll dis[sz][2], center, v1, v2, mx, cnt = -1;
bool used[sz];
vector<vector<ll>> path;
void trav(ll node){
    used[node] = 1;
    path[cnt].push_back(node);
    for(pll edge: adj[node]){
        if(!used[edge.fi]){
            trav(edge.fi);
        }
    }
}
void dfs(ll node, ll we, ll p){
    if(we > mx){
        v2 = node;
        mx = we;
    }
    for(pll edge: adj[node]){
        if(edge.fi != p){
            dfs(edge.fi, we + edge.se, node);
        }
    }
}
void caldis(ll node, ll we, ll p, ll type){
    dis[node][type] = we;
    for(pll edge: adj[node]){
        if(edge.fi != p){
            caldis(edge.fi, we + edge.se, node, type);
        }
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    ll n = N, m = M, i, j, ans = 0;
    for(i=1;i<=m;i++){
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }
    for(i=0;i<n;i++){
        if(!used[i]){
            cnt++;
            path.push_back(vl(0));
            trav(i);
        }
    }
    array<ll, 3> bp = {-1, -1, -1};
    for(i=0;i<=cnt;i++){
        mx = -1, v1 = -1, v2 = -1;
        dfs(path[i][0], 0, -1);
        v1 = v2;
        mx = -1;
        dfs(v1, 0, -1);
        caldis(v1, 0, -1, 0);caldis(v2, 0, -1, 1);
        ans = max(ans, mx);
        ll pc = path[i][0], pb = max(dis[pc][0], dis[pc][1]);
        for(auto x: path[i]){
            if(max(dis[x][0], dis[x][1]) < pb){
                pb = max(dis[x][0], dis[x][1]);
            }
        }
        ans = max(ans, pb);
        if(pb > bp[0]){
            bp[2] = bp[1];
            bp[1] = bp[0];
            bp[0] = pb;
        }
        else if(pb > bp[1]){
            bp[2] = bp[1];
            bp[1] = pb;
        }
        else if(pb > bp[2]){
            bp[2] = pb;
        }
    }
    if(cnt == 0){
        return max(ans, bp[0]);
    }
    ans = max(ans, bp[0] + bp[1] + L);
    if(bp[2] != -1){
        ans = max(ans, bp[1] + bp[2] + 2*L);
    }
    return ans;

}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:46:25: warning: unused variable 'j' [-Wunused-variable]
   46 |     ll n = N, m = M, i, j, ans = 0;
      |                         ^

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 10768 KB Output is correct
2 Correct 18 ms 10780 KB Output is correct
3 Correct 18 ms 10764 KB Output is correct
4 Correct 17 ms 10768 KB Output is correct
5 Correct 18 ms 10768 KB Output is correct
6 Correct 23 ms 12560 KB Output is correct
7 Correct 21 ms 11168 KB Output is correct
8 Correct 19 ms 10768 KB Output is correct
9 Correct 17 ms 10768 KB Output is correct
10 Correct 19 ms 11024 KB Output is correct
11 Correct 1 ms 5212 KB Output is correct
12 Correct 8 ms 10760 KB Output is correct
13 Correct 9 ms 11536 KB Output is correct
14 Correct 8 ms 11024 KB Output is correct
15 Correct 7 ms 11280 KB Output is correct
16 Correct 8 ms 12044 KB Output is correct
17 Correct 8 ms 11280 KB Output is correct
18 Correct 8 ms 11024 KB Output is correct
19 Correct 10 ms 11536 KB Output is correct
20 Correct 1 ms 5208 KB Output is correct
21 Correct 1 ms 5448 KB Output is correct
22 Correct 1 ms 5468 KB Output is correct
23 Correct 8 ms 10764 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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