oj.uz

Submission #964607

# Submission time Handle Problem Language Result Execution time Memory
964607 2024-04-17T07:57:02 Z unkn0t Factories (JOI14_factories) C++17
0 / 100
 8000 ms 206796 KB 
#include "factories.h"
#include <bits/stdc++.h>

#ifdef DEBUG
    #include <debug.hpp>
#else
    #define debug(...) 42
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;

const ll INF = 1e18;
#define MAX_N          500000

vector<pair<int, ll>> gr[MAX_N];
int sz[MAX_N], used[MAX_N], act[MAX_N], cur[MAX_N];
ll cls[MAX_N];
int cent[MAX_N][20];
ll dist[MAX_N][20];
int now = 1;

int find_sz(int v, int p) {
    sz[v] = 1;
    for (auto [to, w] : gr[v]) {
        if (used[to] || to == p) continue;
        sz[v] += find_sz(to, v);
    }
    return sz[v];
}

int centr(int v, int p, int cn) {
    bool flag = 1;
    while (flag) {
        flag = 0;
        for (auto [to, w] : gr[v]) {
            if (used[to] || to == p) continue;
            if (sz[to] > cn / 2) {
                p = v;
                v = to;
                flag = 1;
                break;
            }
        }
    }
    return v;
}

void dfs(int v, int c, int p = -1, ll d = 0) {
    cent[v][cur[v]] = c;
    dist[v][cur[v]] = d;
    ++cur[v];
    for (auto [to, w] : gr[v]) {
        if (used[to] || to == p) continue;
        dfs(to, c, v, d + w);
    }
} 

void Decomp(int v) {
    int cn = find_sz(v, v);
    int c = centr(v, v, cn); 
    used[c] = 1;
    dfs(c, c);
    for (auto [to, w] : gr[c]) {
        if (used[to]) continue;
        Decomp(to);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N; ++i) {
        gr[A[i]].emplace_back(B[i], D[i]);
        gr[B[i]].emplace_back(A[i], D[i]);
    }

    Decomp(0);
}

void Update(int v) {
    for (size_t j = 0; j < cur[v]; ++j) {
        int c = cent[v][j];
        if (act[c] == now) {
            cls[c] = min(cls[c], dist[v][j]);
        } else {
            cls[c] = dist[v][j]; 
            act[c] = now;
        }
    }
}

ll GetMin(int v) {
    ll res = INF;
    for (size_t j = 0; j < cur[v]; ++j) {
        int c = cent[v][j];
        if (act[c] == now) {
            res = min(res, dist[v][j] + cls[c]);
        }
    }
    return res;
}

ll Query(int S, int X[], int T, int Y[]) {
    // go through all X[i] centroids and update cls  
    for (int i = 0; i < S; ++i) {
        Update(X[i]);
    }

    // go through all Y[i] centroids and update min(res, dist[Y[i]][c] + cls[c])
    ll res = INF;
    for (int i = 0; i < T; ++i) {
        res = min(res, GetMin(Y[i])); 
    }

    // Update actuality
    ++now;

    return res;
}

Compilation message

factories.cpp: In function 'void Update(int)':
factories.cpp:82:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |     for (size_t j = 0; j < cur[v]; ++j) {
      |                        ~~^~~~~~~~
factories.cpp: In function 'll GetMin(int)':
factories.cpp:95:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |     for (size_t j = 0; j < cur[v]; ++j) {
      |                        ~~^~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37464 KB Output is correct
2 Correct 210 ms 53460 KB Output is correct
3 Correct 209 ms 53508 KB Output is correct
4 Correct 212 ms 53328 KB Output is correct
5 Incorrect 256 ms 53712 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37468 KB Output is correct
2 Correct 1611 ms 206796 KB Output is correct
3 Execution timed out 8037 ms 203732 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37464 KB Output is correct
2 Correct 210 ms 53460 KB Output is correct
3 Correct 209 ms 53508 KB Output is correct
4 Correct 212 ms 53328 KB Output is correct
5 Incorrect 256 ms 53712 KB Output isn't correct
6 Halted 0 ms 0 KB -