oj.uz

Submission #575675

# Submission time Handle Problem Language Result Execution time Memory
575675 2022-06-11T07:50:34 Z Mazaalai Dreaming (IOI13_dreaming) C++17
32 / 100
 67 ms 24812 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;
        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;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 24812 KB Output is correct
2 Correct 54 ms 24784 KB Output is correct
3 Correct 41 ms 17100 KB Output is correct
4 Correct 9 ms 5844 KB Output is correct
5 Correct 7 ms 4052 KB Output is correct
6 Correct 13 ms 7488 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 26 ms 9408 KB Output is correct
9 Correct 33 ms 12880 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 54 ms 15460 KB Output is correct
12 Correct 67 ms 20044 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 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 1 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 60 ms 24812 KB Output is correct
2 Correct 54 ms 24784 KB Output is correct
3 Correct 41 ms 17100 KB Output is correct
4 Correct 9 ms 5844 KB Output is correct
5 Correct 7 ms 4052 KB Output is correct
6 Correct 13 ms 7488 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 26 ms 9408 KB Output is correct
9 Correct 33 ms 12880 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 54 ms 15460 KB Output is correct
12 Correct 67 ms 20044 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Incorrect 1 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 26 ms 6840 KB Output is correct
2 Correct 26 ms 6812 KB Output is correct
3 Correct 29 ms 6808 KB Output is correct
4 Correct 26 ms 6740 KB Output is correct
5 Correct 34 ms 6772 KB Output is correct
6 Correct 28 ms 7540 KB Output is correct
7 Correct 38 ms 6900 KB Output is correct
8 Correct 26 ms 6728 KB Output is correct
9 Correct 25 ms 6672 KB Output is correct
10 Correct 28 ms 6904 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 15 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 5012 KB Output is correct
16 Correct 13 ms 4812 KB Output is correct
17 Correct 13 ms 4556 KB Output is correct
18 Correct 14 ms 5116 KB Output is correct
19 Correct 13 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 13 ms 4940 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 1 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 60 ms 24812 KB Output is correct
2 Correct 54 ms 24784 KB Output is correct
3 Correct 41 ms 17100 KB Output is correct
4 Correct 9 ms 5844 KB Output is correct
5 Correct 7 ms 4052 KB Output is correct
6 Correct 13 ms 7488 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 26 ms 9408 KB Output is correct
9 Correct 33 ms 12880 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 54 ms 15460 KB Output is correct
12 Correct 67 ms 20044 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Incorrect 1 ms 2644 KB Output isn't correct
17 Halted 0 ms 0 KB -