oj.uz

Submission #587461

# Submission time Handle Problem Language Result Execution time Memory
587461 2022-07-01T23:00:35 Z gg123_pe Roadside Advertisements (NOI17_roadsideadverts) C++14
7 / 100
 83 ms 9676 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[u] 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);

        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]];
        }
    
        cout << ans << "\n";
    }
    return 0; 
}

Compilation message

roadsideadverts.cpp: In function 'bool is(int, int)':
roadsideadverts.cpp:32:19: warning: self-comparison always evaluates to true [-Wtautological-compare]
   32 |     return tin[u] <= tin[u] and tout[u] >= tout[v];
      |            ~~~~~~ ^~ ~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 23.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 7716 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 Incorrect 83 ms 9676 KB Output isn't correct
3 Halted 0 ms 0 KB -