oj.uz

Submission #406695

# Submission time Handle Problem Language Result Execution time Memory
406695 2021-05-18T03:11:27 Z Joshc Islands (IOI08_islands) C++11
90 / 100
 1177 ms 131076 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int MAX_N = 1000001;

#define ll long long

int t[MAX_N], l[MAX_N], vis[MAX_N];
ll dist[MAX_N];
bool cycle[MAX_N];
vector<int> edges[MAX_N];
ll ans = 0;
vector<int> cur;

void dfs2(int x, int p, ll d) {
    cur.push_back(x);
    dist[x] = d;
    for (int i : edges[x]) {
        if (!cycle[i] && i != p) dfs2(i, x, d+(t[x]==i ? l[x] : l[i]));
    }
}

void dfs3(int x, int p, ll d) {
    dist[x] = d;
    for (int i : edges[x]) {
        if ((!cycle[x] || !cycle[i]) && i != p) dfs3(i, x, d+(t[x]==i ? l[x] : l[i]));
    }
}

void solve(vector<int> cyc) {
    ll best = 0, len = 0, psa = 0, x = -1e9, y = -1e9;
    for (int i : cyc) len += l[i];
    for (int i : cyc) {
        cur.clear();
        dfs2(i, i, 0);
        ll m = -1;
        int b;
        for (int j : cur) {
            if (dist[j] > m) {
                m = dist[j];
                b = j;
            }
        }
        best = max(best, max(psa+m+x, len+m-psa+y));
        x = max(x, m-psa);
        y = max(y, m+psa);
        psa += l[i];
        dfs3(b, b, 0);
        ll diameter = -1;
        for (int j : cur) diameter = max(diameter, dist[j]);
        best = max(best, diameter);
    }
    ans += best;
}

void dfs(int v, int c) {
    vis[v] = c;
    if (vis[t[v]] == c && !cycle[t[v]]) {
        vector<int> cyc = {v}, psa;
        for (int i=t[v]; i!=v; i=t[i]) cyc.push_back(i);
        for (int i : cyc) cycle[i] = true;
        solve(cyc);
    }
    if (vis[t[v]] == -1) dfs(t[v], c);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        scanf("%d%d", &t[i], &l[i]);
        cycle[i] = false;
        vis[i] = -1;
        edges[i].push_back(t[i]);
        edges[t[i]].push_back(i);
    }
    for (int i=1; i<=n; i++) {
        if (vis[i] == -1) dfs(i, i);
    }
    printf("%lld\n", ans);
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
islands.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         scanf("%d%d", &t[i], &l[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
islands.cpp: In function 'void solve(std::vector<int>)':
islands.cpp:50:13: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |         dfs3(b, b, 0);
      |         ~~~~^~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23772 KB Output is correct
2 Correct 16 ms 23756 KB Output is correct
3 Correct 16 ms 23796 KB Output is correct
4 Correct 16 ms 23740 KB Output is correct
5 Correct 16 ms 23756 KB Output is correct
6 Correct 16 ms 23776 KB Output is correct
7 Correct 16 ms 23792 KB Output is correct
8 Correct 16 ms 23720 KB Output is correct
9 Correct 16 ms 23756 KB Output is correct
10 Correct 16 ms 23756 KB Output is correct
11 Correct 16 ms 23820 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23868 KB Output is correct
2 Correct 18 ms 23796 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23872 KB Output is correct
2 Correct 18 ms 24012 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24784 KB Output is correct
2 Correct 34 ms 26092 KB Output is correct
3 Correct 27 ms 25296 KB Output is correct
4 Correct 21 ms 24428 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 27144 KB Output is correct
2 Correct 54 ms 30332 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 37012 KB Output is correct
2 Correct 108 ms 39052 KB Output is correct
3 Correct 127 ms 41728 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 49996 KB Output is correct
2 Correct 212 ms 57144 KB Output is correct
3 Correct 236 ms 63720 KB Output is correct
4 Correct 281 ms 69304 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 99040 KB Output is correct
2 Correct 779 ms 95668 KB Output is correct
3 Correct 339 ms 76340 KB Output is correct
4 Correct 412 ms 89492 KB Output is correct
5 Correct 409 ms 88844 KB Output is correct
6 Correct 1177 ms 93188 KB Output is correct
7 Correct 430 ms 95364 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 416 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -