oj.uz

Submission #587462

# Submission time Handle Problem Language Result Execution time Memory
587462 2022-07-01T23:01:13 Z gg123_pe Roadside Advertisements (NOI17_roadsideadverts) C++14
30 / 100
 100 ms 10992 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]];
        }
        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 85 ms 8560 KB Output is correct
2 Correct 87 ms 10916 KB Output is correct
3 Correct 85 ms 10940 KB Output is correct
4 Correct 86 ms 10892 KB Output is correct
5 Correct 88 ms 10884 KB Output is correct
6 Correct 85 ms 10992 KB Output is correct
7 Correct 90 ms 10956 KB Output is correct
8 Correct 86 ms 10940 KB Output is correct
9 Correct 95 ms 10884 KB Output is correct
10 Correct 100 ms 10896 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 7040 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 85 ms 8560 KB Output is correct
3 Correct 87 ms 10916 KB Output is correct
4 Correct 85 ms 10940 KB Output is correct
5 Correct 86 ms 10892 KB Output is correct
6 Correct 88 ms 10884 KB Output is correct
7 Correct 85 ms 10992 KB Output is correct
8 Correct 90 ms 10956 KB Output is correct
9 Correct 86 ms 10940 KB Output is correct
10 Correct 95 ms 10884 KB Output is correct
11 Correct 100 ms 10896 KB Output is correct
12 Incorrect 68 ms 7040 KB Output isn't correct
13 Halted 0 ms 0 KB -