oj.uz

Submission #765202

# Submission time Handle Problem Language Result Execution time Memory
765202 2023-06-24T09:20:20 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
7 / 100
 1000 ms 8344 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
// mt19937 rnd  (chrono::steady_clock::now().time_since_epoch().count());
#define sz(s) int(s.size())
#define ll long long
#define ull unsigned long long
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(), v.end()
// #define int ll
#define all(v) v.begin(), v.end()
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout)
const int N=5e4+7, mod=1e9+7, Mod=998244353;
vector<vector<pair<int, int> > > g(N);
ll ans=0, dp[N];
int f[N];
void dfs(int v, int cnt, int p) {
    for(auto to : g[v]) {
        if(to.F!=p) {
            dp[to.F]=dp[v]+to.S;
            if(f[to.F]) {
                dfs(to.F, to.F, v);
                ans+=dp[to.F]-dp[cnt];
                // cout << v << ' ' << cnt << ' ' << dp[v] << ' ' << dp[cnt] << '\n';
            }else {
                dfs(to.F, cnt, v);
            }
        }
    }
}
void solve() {
    int n;
    cin>>n;
    for(int i=1; i<n; i++) {
        int x, y, w;
        cin>>x>>y>>w;
        g[x].pb({y, w});
        g[y].pb({x, w});
        // if(x>y)swap(x, y);
        // mp[{x, y}]=i;
    }
    int q;
    cin>>q;
    while(q--) {
        ans=0;
        int a, b, c, d, e;
        cin>>a>>b>>c>>d>>e;
        for(int i=0; i<=n; i++)f[i]=0;
        f[a]=1, f[b]=1, f[c]=1, f[d]=1, f[e]=1;
        dp[a]=0;
        dfs(a, a, a);
        cout << ans << '\n'; 
    }
}   
signed main() {
    // file("floor4");
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T=1;
    // cin>>T;
    while(T--)solve();
}

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 Execution timed out 1077 ms 8344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 3924 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 Execution timed out 1077 ms 8344 KB Time limit exceeded
3 Halted 0 ms 0 KB -