oj.uz

Submission #1100140

# Submission time Handle Problem Language Result Execution time Memory
1100140 2024-10-12T22:47:36 Z CpDark Roadside Advertisements (NOI17_roadsideadverts) C++17
30 / 100
 40 ms 10204 KB 
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vp;
typedef vector<vp> vvp;

vvp graph;
vi deg;
vi id;
vi line;
vi prefix;

int rangeSum(int s, int e) {
    if (s == 0)return prefix[e];
    return prefix[e] - prefix[s - 1];
}

void dfs(int v, int p, int counter) {
    id[v] = counter;
    for (pii curr : graph[v]) {
        int u = curr.first;
        int w = curr.second;
        if (u == p)continue;
        line.push_back(w);
        dfs(u, v, counter + 1);
    }
}

void init(int N, vector<int> V, vector<int> U, vector<int> W) {
    graph.resize(N);
    prefix.resize(N - 1);
    deg.resize(N);
    id.resize(N);
    for (int i = 0;i < N - 1;i++) {
        graph[V[i]].push_back({ U[i],W[i] });
        graph[U[i]].push_back({ V[i],W[i] });
        deg[V[i]]++; deg[U[i]]++;
    }

    int start = 0;
    for (int i = 0;i < N;i++) {
        start = i;
        if (deg[i] == 1)break;
    }

    dfs(start, start, 0);

    for (int i = 0;i < line.size();i++) {
        if (i != 0) prefix[i] += prefix[i - 1];
        prefix[i] += line[i];
    }
}


int query(int a, int b, int c, int d, int e) {
    int left = min({ id[a],id[b],id[c],id[d], id[e] });
    int right = max({ id[a],id[b],id[c],id[d], id[e] });

    return rangeSum(left, right - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N;

    vi V(N - 1), U(N - 1), W(N - 1);
    for (int i = 0;i < N - 1;i++)cin >> V[i] >> U[i] >> W[i];
    
    init(N, V, U, W);

    cin >> Q;
    for (int i = 0;i < Q;i++) {
        int a, b, c, d, e;
        cin >> a >> b >> c >> d >> e;
        cout << query(a, b, c, d, e) << endl;
    }
    return 0;
}

Compilation message

roadsideadverts.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roadsideadverts.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0;i < line.size();i++) {
      |                    ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 10192 KB Output is correct
2 Correct 31 ms 10204 KB Output is correct
3 Correct 32 ms 9940 KB Output is correct
4 Correct 40 ms 10204 KB Output is correct
5 Correct 34 ms 10204 KB Output is correct
6 Correct 35 ms 9940 KB Output is correct
7 Correct 37 ms 9984 KB Output is correct
8 Correct 32 ms 10204 KB Output is correct
9 Correct 33 ms 10196 KB Output is correct
10 Correct 34 ms 10204 KB Output is correct

Subtask #3
0 / 40.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 28 ms 10192 KB Output is correct
3 Correct 31 ms 10204 KB Output is correct
4 Correct 32 ms 9940 KB Output is correct
5 Correct 40 ms 10204 KB Output is correct
6 Correct 34 ms 10204 KB Output is correct
7 Correct 35 ms 9940 KB Output is correct
8 Correct 37 ms 9984 KB Output is correct
9 Correct 32 ms 10204 KB Output is correct
10 Correct 33 ms 10196 KB Output is correct
11 Correct 34 ms 10204 KB Output is correct
12 Incorrect 17 ms 6236 KB Output isn't correct
13 Halted 0 ms 0 KB -