oj.uz

Submission #575616

# Submission time Handle Problem Language Result Execution time Memory
575616 2022-06-11T06:53:23 Z Mazaalai Dreaming (IOI13_dreaming) C++17
32 / 100
 56 ms 14796 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;
    for (auto [a, b] : paths[pos]) {
        if (a == par) continue;
        int x = pre+b, y = sizes[a];
        if (max(pre, suf) > max(x, y)) return findCentroid(a, pos, pre+b);
    }
    return {pos, pre, suf};
}
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]+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';
    }
    sort(ALL(pts), [&](auto&a, auto&b) {
        return a.ss < b.ss;
    });
 
    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 44 ms 14796 KB Output is correct
2 Correct 54 ms 14772 KB Output is correct
3 Correct 35 ms 10608 KB Output is correct
4 Correct 7 ms 4344 KB Output is correct
5 Correct 6 ms 3540 KB Output is correct
6 Correct 11 ms 5332 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 34 ms 6740 KB Output is correct
9 Correct 31 ms 8592 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 42 ms 10188 KB Output is correct
12 Correct 56 ms 12468 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 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 44 ms 14796 KB Output is correct
2 Correct 54 ms 14772 KB Output is correct
3 Correct 35 ms 10608 KB Output is correct
4 Correct 7 ms 4344 KB Output is correct
5 Correct 6 ms 3540 KB Output is correct
6 Correct 11 ms 5332 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 34 ms 6740 KB Output is correct
9 Correct 31 ms 8592 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 42 ms 10188 KB Output is correct
12 Correct 56 ms 12468 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 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 30 ms 6744 KB Output is correct
2 Correct 28 ms 6740 KB Output is correct
3 Correct 44 ms 6804 KB Output is correct
4 Correct 24 ms 6740 KB Output is correct
5 Correct 26 ms 6816 KB Output is correct
6 Correct 43 ms 7444 KB Output is correct
7 Correct 28 ms 7000 KB Output is correct
8 Correct 30 ms 6720 KB Output is correct
9 Correct 27 ms 6740 KB Output is correct
10 Correct 31 ms 6852 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 14 ms 4940 KB Output is correct
13 Correct 14 ms 5060 KB Output is correct
14 Correct 20 ms 4940 KB Output is correct
15 Correct 16 ms 4940 KB Output is correct
16 Correct 14 ms 4812 KB Output is correct
17 Correct 14 ms 4656 KB Output is correct
18 Correct 15 ms 5068 KB Output is correct
19 Correct 19 ms 4884 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 1 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 44 ms 14796 KB Output is correct
2 Correct 54 ms 14772 KB Output is correct
3 Correct 35 ms 10608 KB Output is correct
4 Correct 7 ms 4344 KB Output is correct
5 Correct 6 ms 3540 KB Output is correct
6 Correct 11 ms 5332 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 34 ms 6740 KB Output is correct
9 Correct 31 ms 8592 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 42 ms 10188 KB Output is correct
12 Correct 56 ms 12468 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 2 ms 2644 KB Output isn't correct
17 Halted 0 ms 0 KB -