oj.uz

Submission #587463

# Submission time Handle Problem Language Result Execution time Memory
587463 2022-07-01T23:05:01 Z gg123_pe Roadside Advertisements (NOI17_roadsideadverts) C++14
30 / 100
 107 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[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);

        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; 
}

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
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 8560 KB Output is correct
2 Correct 106 ms 9952 KB Output is correct
3 Correct 85 ms 9944 KB Output is correct
4 Correct 84 ms 9884 KB Output is correct
5 Correct 92 ms 9896 KB Output is correct
6 Correct 107 ms 9876 KB Output is correct
7 Correct 83 ms 9880 KB Output is correct
8 Correct 90 ms 9944 KB Output is correct
9 Correct 84 ms 9908 KB Output is correct
10 Correct 86 ms 9912 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 6968 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 103 ms 8560 KB Output is correct
3 Correct 106 ms 9952 KB Output is correct
4 Correct 85 ms 9944 KB Output is correct
5 Correct 84 ms 9884 KB Output is correct
6 Correct 92 ms 9896 KB Output is correct
7 Correct 107 ms 9876 KB Output is correct
8 Correct 83 ms 9880 KB Output is correct
9 Correct 90 ms 9944 KB Output is correct
10 Correct 84 ms 9908 KB Output is correct
11 Correct 86 ms 9912 KB Output is correct
12 Incorrect 48 ms 6968 KB Output isn't correct
13 Halted 0 ms 0 KB -