oj.uz

Submission #735117

# Submission time Handle Problem Language Result Execution time Memory
735117 2023-05-03T15:01:31 Z sandry24 Dreaming (IOI13_dreaming) C++17
14 / 100
 242 ms 24716 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+5);
vector<bool> visited(1e5+5);
vi parent(1e5+5);

ll maxe = -1, maxnode = -1;

map<pi, int> cost;

void dfs(ll x, ll p=-1, ll dist=0){
    visited[x] = 1;
    parent[x] = p;
    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]});
        cost[{A[i], B[i]}] = cost[{B[i], A[i]}] = T[i];
    }
    vector<pair<ll, ll>> centers;
    for(int i = 0; i < N; i++){
        if(!visited[i]){
            maxe = 0, maxnode = -1;
            dfs(i);
            if(maxnode == -1){
                centers.pb({0, i});
                continue;
            }
            ll n1 = maxnode;
            maxe = 0, maxnode = -1;
            dfs(n1);
            ll n2 = maxnode;
            vi path;
            while(n2 != n1){
                path.pb(n2);
                n2 = parent[n2];
            }
            path.pb(n2);
            ll cur = 0, best_res = 1e18, best_v = path[0];
            for (int j = 1; j < path.size(); j++) {
                cur += cost[{path[j], path[j - 1]}];
                //cout << cur << '\n';
                if (max(cur, maxe - cur) < best_res) {
                    best_res = max(cur, maxe - cur);
                    best_v = path[j];
                }
            }
            centers.push_back({best_res, best_v});
        }
    }
    /*for(auto i : centers)
        cout << i.f << ' ' << i.s << '\n';
    cout << '\n';*/
    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});
    }
    /*for(int i = 0; i < N; i++){
        cout << i << ":\n";
        for(auto j : adj[i]){
            cout << j.f << ' ' << j.s << '\n';
        }
        cout << '\n';
    }*/
    dfs(0);
    maxe = 0;
    dfs(maxnode);
    return maxe;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:62:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for (int j = 1; j < path.size(); j++) {
      |                             ~~^~~~~~~~~~~~~
dreaming.cpp:77: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]
   77 |     for(int i = 1; i < centers.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 24716 KB Output is correct
2 Correct 184 ms 24644 KB Output is correct
3 Correct 116 ms 17204 KB Output is correct
4 Correct 17 ms 6228 KB Output is correct
5 Correct 15 ms 5120 KB Output is correct
6 Correct 28 ms 7748 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 71 ms 11392 KB Output is correct
9 Correct 120 ms 14364 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 196 ms 18232 KB Output is correct
12 Correct 242 ms 21384 KB Output is correct
13 Correct 3 ms 3156 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3040 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Incorrect 2 ms 3028 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 24716 KB Output is correct
2 Correct 184 ms 24644 KB Output is correct
3 Correct 116 ms 17204 KB Output is correct
4 Correct 17 ms 6228 KB Output is correct
5 Correct 15 ms 5120 KB Output is correct
6 Correct 28 ms 7748 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 71 ms 11392 KB Output is correct
9 Correct 120 ms 14364 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 196 ms 18232 KB Output is correct
12 Correct 242 ms 21384 KB Output is correct
13 Correct 3 ms 3156 KB Output is correct
14 Correct 2 ms 3028 KB Output is correct
15 Correct 2 ms 3040 KB Output is correct
16 Correct 2 ms 3028 KB Output is correct
17 Correct 2 ms 3028 KB Output is correct
18 Correct 2 ms 3028 KB Output is correct
19 Incorrect 2 ms 3028 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 11712 KB Output is correct
2 Correct 71 ms 11720 KB Output is correct
3 Correct 94 ms 11616 KB Output is correct
4 Correct 92 ms 11668 KB Output is correct
5 Correct 75 ms 11664 KB Output is correct
6 Correct 88 ms 12732 KB Output is correct
7 Correct 86 ms 12072 KB Output is correct
8 Correct 73 ms 11448 KB Output is correct
9 Correct 85 ms 11428 KB Output is correct
10 Correct 83 ms 11940 KB Output is correct
11 Correct 1 ms 3028 KB Output is correct
12 Correct 16 ms 8536 KB Output is correct
13 Correct 16 ms 8524 KB Output is correct
14 Correct 17 ms 8476 KB Output is correct
15 Correct 19 ms 8520 KB Output is correct
16 Correct 16 ms 8516 KB Output is correct
17 Correct 14 ms 8516 KB Output is correct
18 Correct 15 ms 8616 KB Output is correct
19 Correct 14 ms 8516 KB Output is correct
20 Runtime error 5 ms 5972 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3040 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Incorrect 2 ms 3028 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 24716 KB Output is correct
2 Correct 184 ms 24644 KB Output is correct
3 Correct 116 ms 17204 KB Output is correct
4 Correct 17 ms 6228 KB Output is correct
5 Correct 15 ms 5120 KB Output is correct
6 Correct 28 ms 7748 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 71 ms 11392 KB Output is correct
9 Correct 120 ms 14364 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 196 ms 18232 KB Output is correct
12 Correct 242 ms 21384 KB Output is correct
13 Correct 3 ms 3156 KB Output is correct
14 Correct 2 ms 3028 KB Output is correct
15 Correct 2 ms 3040 KB Output is correct
16 Correct 2 ms 3028 KB Output is correct
17 Correct 2 ms 3028 KB Output is correct
18 Correct 2 ms 3028 KB Output is correct
19 Incorrect 2 ms 3028 KB Output isn't correct
20 Halted 0 ms 0 KB -