제출 #1333840

#제출 시각아이디문제언어결과실행 시간메모리
1333840gelastropodWind Turbines (EGOI25_windturbines)C++20
8 / 100
758 ms1114112 KiB
#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;

int cnt = 0;
vector<vector<int>> adjlist;
vector<int> pre;

void dfs(int n, int p) {
    pre[n] = cnt++;
    for (int i : adjlist[n]) if (i != p) dfs(i, n);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N, M, Q, a, b, c; cin >> N >> M >> Q;
    vector<long long> funny(N, 0);
    adjlist.resize(N, vector<int>());
    pre.resize(N, 0);
    vector<pair<int, pair<int, int>>> edges;
    for (int i = 0; i < M; i++) {
        cin >> a >> b >> c;
        adjlist[a].push_back(b);
        adjlist[b].push_back(a);
        edges.push_back({ c, {a, b} });
    }
    dfs(0, -1);
    for (int i = 0; i < M; i++) funny[max(pre[edges[i].second.first], pre[edges[i].second.second])] = edges[i].first;
    for (int i = 1; i < N; i++) funny[i] += funny[i - 1];
    for (int i = 0; i < Q; i++) {
        cin >> a >> b;
        cout << funny.back() - funny[b] + funny[a] << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...