oj.uz

Submission #780036

# Submission time Handle Problem Language Result Execution time Memory
780036 2023-07-12T05:54:49 Z cheat_when_I_was_young Factories (JOI14_factories) C++17
0 / 100
 9 ms 12500 KB 
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;

const int NM = 5e5 + 5;

int in[NM], d[NM], h[NM];
vector<int> tour;
vector<pair<int,int>> adj[NM];

void dfs(int u, int par) {
    in[u] = tour.size();
    tour.push_back(u);
    for (auto &vv: adj[u]) {
        int v = vv.first, w = vv.second;
        if (v == par) continue;
        d[v] = d[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u);
    }
    tour.push_back(u);
}

const int LG = __lg(NM) + 1;

pair<int,int> ST[LG][NM];

void build() {
    for (int i = 0; i < tour.size(); ++i)
        ST[0][i] = {h[tour[i]], tour[i]};
    for (int j = 1; j < LG; ++j)
        for (int i = 0; i + (1<<j) - 1 < tour.size(); ++i)
            ST[j][i] = min(ST[j-1][i], ST[j-1][i + (1<<(j-1))]);
}

int lca(int l, int r) {
    int k = __lg(r - l + 1);
    return min(ST[k][l], ST[k][r - (1<<k) + 1]).second;
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N-1; ++i) {
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    dfs(1, 1);
    build();
}

long long Query(int S, int X[], int T, int Y[]) {
    return 0;
}

Compilation message

factories.cpp: In function 'void build()':
factories.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < tour.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
factories.cpp:32:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int i = 0; i + (1<<j) - 1 < tour.size(); ++i)
      |                         ~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 12244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12500 KB Output isn't correct
2 Halted 0 ms 0 KB -