oj.uz

Submission #575670

# Submission time Handle Problem Language Result Execution time Memory
575670 2022-06-11T07:41:54 Z Mazaalai Dreaming (IOI13_dreaming) C++17
32 / 100
 66 ms 24864 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ALL(x) x.begin(),x.end()
using namespace std;
using VI = vector <int>;
using PII = pair <int, int>;
const int N = 1e5+5;
vector <PII> paths[N];
bool vis[N];
int n, m, L, sizes[N], len;
PII dp[N];
 
PII getFarthest(int pos, int par = 0) {
    dp[pos] = {0, pos};
    for (auto [a, b] : paths[pos]) {
        if (a == par) continue;
        PII tmp = getFarthest(a, pos);
        if (dp[pos].ff < tmp.ff + b) dp[pos] = {tmp.ff + b, tmp.ss};
    }
    return dp[pos];
}
int getSizes(int pos, int par = 0) {
    vis[pos] = 1;
    for (auto [a, b] : paths[pos]) {
        if (a == par) continue;
        sizes[pos] = max(sizes[pos], b + getSizes(a, pos));
    }
    return sizes[pos];
}
VI findCentroid(int pos, int par = 0, int pre = 0) {
    int suf = len - pre;
    VI res = {pos, pre, suf};
    for (auto [a, b] : paths[pos]) {
        if (a == par) continue;
        int x = pre+b, y = sizes[a];
        // if (max(pre, suf) >= max(x, y)) {
            VI tmp = findCentroid(a, pos, pre+b);
            if (max(pre, suf) > max(tmp[1], tmp[2])) res = tmp;
        // }
    }
    return res;
}
VI getCentroid(int pos) {
    len = getSizes(pos);
    return findCentroid(pos);
}
int travelTime(int _N, int _M, int _L, int _A[], int _B[], int _T[]) {
    n = _N;
    m = _M;
    L = _L;
    vector <PII> pts;
    for (int i = 0; i < _M; i++) {
        // paths[_A[i]].pb({_B[i], _T[i]});
        // paths[_B[i]].pb({_A[i], _T[i]});
        paths[_A[i]+1].pb({_B[i]+1, _T[i]});
        paths[_B[i]+1].pb({_A[i]+1, _T[i]});
    }
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        PII tmp = getFarthest(i);
        VI point = getCentroid(tmp.ss);
        if (point[1] < point[2]) swap(point[1], point[2]);
        pts.pb({point[1], point[2]});
        // cout << i-1 << ": " << point[0]-1 << ' ' << point[1] << ' ' << point[2] << '\n';
        // cout << i << ": " << point[0] << ' ' << point[1] << ' ' << point[2] << '\n';
    }
    // sort(ALL(pts), [&](auto&a, auto&b) {
    //     return max(a.ff, a.ss) < max(b.ff, b.ss);
    // });
    sort(ALL(pts));
    n = pts.size();
    for (int i = n-2; i >= 0; i--) {
        PII&a = pts[n-1];
        PII&b = pts[i];
        if (a.ff > a.ss) swap(a.ff, a.ss);
        if (b.ff > b.ss) swap(b.ff, b.ss);
        // cout << a.ff << ',' << a.ss << ' ' << b.ff << ',' << b.ss << " -> "; 
        VI x = {a.ff, a.ss, b.ss+L};
        VI y = {b.ff, b.ss, a.ss+L};
        sort(ALL(x));
        sort(ALL(y));
        a = {x[1], x[2]};
        b = {y[1], y[2]};
        a = max(a, b);
        // cout << a.ff << ',' << a.ss << "\n"; 
    }
    // cout << pts[n-1].ff+pts[n-1].ss << '\n';
    return pts[n-1].ff+pts[n-1].ss;
}

Compilation message

dreaming.cpp: In function 'VI findCentroid(int, int, int)':
dreaming.cpp:38:13: warning: unused variable 'x' [-Wunused-variable]
   38 |         int x = pre+b, y = sizes[a];
      |             ^
dreaming.cpp:38:24: warning: unused variable 'y' [-Wunused-variable]
   38 |         int x = pre+b, y = sizes[a];
      |                        ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 24864 KB Output is correct
2 Correct 57 ms 24732 KB Output is correct
3 Correct 36 ms 17184 KB Output is correct
4 Correct 8 ms 5844 KB Output is correct
5 Correct 6 ms 4180 KB Output is correct
6 Correct 13 ms 7528 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 25 ms 9424 KB Output is correct
9 Correct 41 ms 12976 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 51 ms 15452 KB Output is correct
12 Correct 66 ms 19964 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 24864 KB Output is correct
2 Correct 57 ms 24732 KB Output is correct
3 Correct 36 ms 17184 KB Output is correct
4 Correct 8 ms 5844 KB Output is correct
5 Correct 6 ms 4180 KB Output is correct
6 Correct 13 ms 7528 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 25 ms 9424 KB Output is correct
9 Correct 41 ms 12976 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 51 ms 15452 KB Output is correct
12 Correct 66 ms 19964 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Incorrect 2 ms 2644 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6764 KB Output is correct
2 Correct 30 ms 6868 KB Output is correct
3 Correct 28 ms 6796 KB Output is correct
4 Correct 33 ms 6740 KB Output is correct
5 Correct 28 ms 6856 KB Output is correct
6 Correct 28 ms 7476 KB Output is correct
7 Correct 27 ms 7000 KB Output is correct
8 Correct 25 ms 6664 KB Output is correct
9 Correct 25 ms 6736 KB Output is correct
10 Correct 26 ms 6872 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 14 ms 4940 KB Output is correct
13 Correct 14 ms 5068 KB Output is correct
14 Correct 14 ms 4940 KB Output is correct
15 Correct 14 ms 4940 KB Output is correct
16 Correct 13 ms 4940 KB Output is correct
17 Correct 14 ms 4556 KB Output is correct
18 Correct 14 ms 5068 KB Output is correct
19 Correct 14 ms 4940 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 2 ms 2772 KB Output is correct
23 Correct 14 ms 4940 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 24864 KB Output is correct
2 Correct 57 ms 24732 KB Output is correct
3 Correct 36 ms 17184 KB Output is correct
4 Correct 8 ms 5844 KB Output is correct
5 Correct 6 ms 4180 KB Output is correct
6 Correct 13 ms 7528 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 25 ms 9424 KB Output is correct
9 Correct 41 ms 12976 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 51 ms 15452 KB Output is correct
12 Correct 66 ms 19964 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Incorrect 2 ms 2644 KB Output isn't correct
17 Halted 0 ms 0 KB -