oj.uz

Submission #587464

# Submission time Handle Problem Language Result Execution time Memory
587464 2022-07-01T23:06:27 Z gg123_pe Roadside Advertisements (NOI17_roadsideadverts) C++14
30 / 100
 118 ms 9952 KB 
#include <bits/stdc++.h>
using namespace std; 
 
typedef long long ll; 
#define f(i,a,b) for(ll i = a; i < b; i++)
#define fa(i,a,b) for(ll i = a; i >= b; i--)

const int N = 50005; 
const ll inf = 2e18; 


int n, a[6], d[N], tin[N], tout[N], c, p[N][16]; 
vector <pair<int,int>> adj[N]; 
vector <int> aux; 

void dfs(int u, int f){
    p[u][0] = f; 
    f(i,1,16) p[u][i] = p[p[u][i-1]][i-1];

    tin[u] = c++; 

    for(auto p: adj[u]){
        int v = p.first, w = p.second; 
        if(v == f) continue; 
        d[v] = d[u] + w; 
        dfs(v, u); 
    }
    tout[u] = c++;
}

bool is(int u, int v){
    return tin[u] <= tin[v] and tout[u] >= tout[v]; 
}

int lca(int u, int v){
    if(is(u, v)) return u; 
    if(is(v, u)) return v; 

    fa(i,15,0){
        if(p[u][i] == 0 or is(p[u][i], v)) continue; 
        u = p[u][i];
    }
    return p[u][0];
}
int main(){
    cin >> n; 

    f(i,1,n){
        int u, v, w; 
        cin >> u >> v >> w; 

        adj[u].push_back({v, w}); 
        adj[v].push_back({u, w}); 
    }

    dfs(0, -1); 

    int qe; cin >> qe; 

    while(qe--){
        bool fe = 0; 
        vector <pair<int,int>> v; 
        set <int> s; 

        f(i,1,6){
            cin >> a[i]; 
            if(a[i] == 0) fe = 1; 
            v.push_back({tin[a[i]], a[i]});
            s.insert(a[i]);
        }

        if(!fe){
            v.push_back({tin[0], 0}); 
            s.insert(0);
        }

        sort(v.begin(), v.end()); 

        int ans = 0, l = v.size(); 

        f(i,1,l){
            s.insert(lca(v[i].second, v[i-1].second));
        }

        v.clear(); 
        for(int x: s) v.push_back({tin[x], x}); 

        sort(v.begin(), v.end()); 

        stack <int> q; 
        q.push(0);

        l = v.size();

        f(i,1,l){
            int vi = v[i].second; 
            while(1){
                int x = q.top();
                if(is(x, vi)){
                    ans += d[vi] - d[x];
                    if(x == 0){
                        aux.push_back(vi);
                    }
                    q.push(vi);
                    break; 
                }
                q.pop();
            }
        }
        if(aux.size() == 1 and !fe){
            ans -= d[aux[0]];
        }
        aux.clear();
        cout << ans << "\n";
    }
    return 0; 
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 8376 KB Output is correct
2 Correct 118 ms 9908 KB Output is correct
3 Correct 104 ms 9928 KB Output is correct
4 Correct 101 ms 9888 KB Output is correct
5 Correct 82 ms 9876 KB Output is correct
6 Correct 90 ms 9932 KB Output is correct
7 Correct 92 ms 9952 KB Output is correct
8 Correct 87 ms 9940 KB Output is correct
9 Correct 91 ms 9924 KB Output is correct
10 Correct 97 ms 9912 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 7044 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 1492 KB Output is correct
2 Correct 94 ms 8376 KB Output is correct
3 Correct 118 ms 9908 KB Output is correct
4 Correct 104 ms 9928 KB Output is correct
5 Correct 101 ms 9888 KB Output is correct
6 Correct 82 ms 9876 KB Output is correct
7 Correct 90 ms 9932 KB Output is correct
8 Correct 92 ms 9952 KB Output is correct
9 Correct 87 ms 9940 KB Output is correct
10 Correct 91 ms 9924 KB Output is correct
11 Correct 97 ms 9912 KB Output is correct
12 Incorrect 52 ms 7044 KB Output isn't correct
13 Halted 0 ms 0 KB -