oj.uz

답안 #735125

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
735125 2023-05-03T15:06:31 Z sandry24 꿈 (IOI13_dreaming) C++17
32 / 100
 65 ms 15168 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
 
vector<vector<pi>> adj(1e5+1);
vector<bool> visited(1e5+1);
vi parent(1e5+1), dists(1e5+1);
 
ll maxe = -1, maxnode = -1;
 
void dfs(ll x, ll p=-1, ll dist=0){
    visited[x] = 1;
    parent[x] = p;
    dists[x] = dist;
    if(dist > maxe){
        maxe = dist;
        maxnode = x;
    }
    for(auto i : adj[x]){
        if(i.f != p)
            dfs(i.f, x, dist + i.s);
    }
}
 
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    for(int i = 0; i < M; i++){
        adj[A[i]].pb({B[i], T[i]});
        adj[B[i]].pb({A[i], T[i]});
    }
    vector<pair<ll, ll>> centers;
    for(int i = 0; i < N; i++){
        if(!visited[i]){
            maxe = -1, maxnode = -1;
            dfs(i);
            ll n1 = maxnode;
            maxe = -1, maxnode = -1;
            dfs(n1);
            ll n2 = maxnode;
            vector<pair<ll, ll>> path;
            while(n2 != n1){
                path.pb({n2, dists[n2]});
                n2 = parent[n2];
            }
            path.pb({n2, dists[n2]});
            reverse(path.begin(), path.end());
            ll diameter = path.back().second;
            ll best_node = path[0].f, best_dist = 1e18;
            for(int j = 0; j < path.size(); j++){
                if(max(path[j].s, diameter - path[j].s) < best_dist){
                    best_node = path[j].f;
                    best_dist = max(path[j].s, diameter - path[j].s);
                }
            }
            centers.pb({best_dist, best_node});
        }
    }
    sort(centers.begin(), centers.end(), greater<pair<ll, ll>>());
    for(int i = 1; i < centers.size(); i++){
        adj[centers[0].s].pb({centers[i].s, L});
        adj[centers[i].s].pb({centers[0].s, L});
    }
    dfs(0);
    maxe = -1;
    dfs(maxnode);
    return dists[maxnode];
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:58:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for(int j = 0; j < path.size(); j++){
      |                            ~~^~~~~~~~~~~~~
dreaming.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 1; i < centers.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 15168 KB Output is correct
2 Correct 61 ms 15124 KB Output is correct
3 Correct 38 ms 10828 KB Output is correct
4 Correct 9 ms 5216 KB Output is correct
5 Correct 8 ms 4356 KB Output is correct
6 Correct 15 ms 6172 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 29 ms 7356 KB Output is correct
9 Correct 34 ms 9228 KB Output is correct
10 Correct 2 ms 3540 KB Output is correct
11 Correct 53 ms 10580 KB Output is correct
12 Correct 65 ms 13340 KB Output is correct
13 Correct 2 ms 3540 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Incorrect 2 ms 3412 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 15168 KB Output is correct
2 Correct 61 ms 15124 KB Output is correct
3 Correct 38 ms 10828 KB Output is correct
4 Correct 9 ms 5216 KB Output is correct
5 Correct 8 ms 4356 KB Output is correct
6 Correct 15 ms 6172 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 29 ms 7356 KB Output is correct
9 Correct 34 ms 9228 KB Output is correct
10 Correct 2 ms 3540 KB Output is correct
11 Correct 53 ms 10580 KB Output is correct
12 Correct 65 ms 13340 KB Output is correct
13 Correct 2 ms 3540 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 2 ms 3412 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 2 ms 3412 KB Output is correct
18 Correct 2 ms 3412 KB Output is correct
19 Incorrect 2 ms 3412 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 8208 KB Output is correct
2 Correct 43 ms 8128 KB Output is correct
3 Correct 43 ms 8108 KB Output is correct
4 Correct 37 ms 8132 KB Output is correct
5 Correct 37 ms 8132 KB Output is correct
6 Correct 41 ms 8884 KB Output is correct
7 Correct 36 ms 8408 KB Output is correct
8 Correct 33 ms 8056 KB Output is correct
9 Correct 34 ms 8072 KB Output is correct
10 Correct 38 ms 8392 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 19 ms 8900 KB Output is correct
13 Correct 19 ms 8900 KB Output is correct
14 Correct 19 ms 8900 KB Output is correct
15 Correct 19 ms 8900 KB Output is correct
16 Correct 21 ms 9028 KB Output is correct
17 Correct 19 ms 8900 KB Output is correct
18 Correct 20 ms 8852 KB Output is correct
19 Correct 20 ms 8900 KB Output is correct
20 Correct 2 ms 3412 KB Output is correct
21 Correct 2 ms 3412 KB Output is correct
22 Correct 2 ms 3540 KB Output is correct
23 Correct 19 ms 8896 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Incorrect 2 ms 3412 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 15168 KB Output is correct
2 Correct 61 ms 15124 KB Output is correct
3 Correct 38 ms 10828 KB Output is correct
4 Correct 9 ms 5216 KB Output is correct
5 Correct 8 ms 4356 KB Output is correct
6 Correct 15 ms 6172 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 29 ms 7356 KB Output is correct
9 Correct 34 ms 9228 KB Output is correct
10 Correct 2 ms 3540 KB Output is correct
11 Correct 53 ms 10580 KB Output is correct
12 Correct 65 ms 13340 KB Output is correct
13 Correct 2 ms 3540 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 2 ms 3412 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 2 ms 3412 KB Output is correct
18 Correct 2 ms 3412 KB Output is correct
19 Incorrect 2 ms 3412 KB Output isn't correct
20 Halted 0 ms 0 KB -