oj.uz

Submission #950771

# Submission time Handle Problem Language Result Execution time Memory
950771 2024-03-20T16:41:17 Z Irate Roadside Advertisements (NOI17_roadsideadverts) C++17
47 / 100
 1000 ms 8812 KB 
#include<bits/stdc++.h>
using namespace std;
const int mxN = 5e4 + 5;

vector<pair<int, int>> G[mxN];
vector<int>path, W;
vector<bool>edge;
int p[5];
void dfs(int node, int par){
    bool check = 0;
    for(int i = 0;i < 5;++i){
        check |= (node == p[i]);
    }
    if(check){
        for(int &i : path){
            edge[i] = 1;
        }
    }
    for(auto i : G[node]){
        int to = i.first, indx = i.second;
        if(to != par){
            path.push_back(indx);
            dfs(to, node);
            path.pop_back();
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    W.resize(n);
    for(int i = 1;i < n;++i){
        int u, v, w;
        cin >> u >> v >> w;
        W[i - 1] = w;
        G[u].push_back({v, i - 1});
        G[v].push_back({u, i - 1});
    }
    edge.resize(n);
    int q;
    cin >> q;
    while(q--){
        for(int i = 0;i < n;++i){
            edge[i] = 0;
        }
        for(int i = 0;i < 5;++i){
            cin >> p[i];
        }
        dfs(p[0], p[0]);
        long long res = 0;
        for(int i = 0;i < n;++i){
            if(edge[i])res += W[i];
        }
        cout << res << '\n';
    }
}

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 8812 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 4444 KB Output is correct
2 Correct 228 ms 7712 KB Output is correct
3 Correct 228 ms 7476 KB Output is correct
4 Correct 244 ms 7696 KB Output is correct
5 Correct 230 ms 7632 KB Output is correct
6 Correct 231 ms 7720 KB Output is correct
7 Correct 230 ms 7640 KB Output is correct
8 Correct 231 ms 7704 KB Output is correct
9 Correct 237 ms 7684 KB Output is correct
10 Correct 230 ms 7636 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Execution timed out 1044 ms 8812 KB Time limit exceeded
3 Halted 0 ms 0 KB -