제출 #1234005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234005		nasjes	Roadside Advertisements (NOI17_roadsideadverts)	C++20	7 / 100	1095 ms	30764 KiB

roadsideadverts

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 1e6 + 10;
//const ll mod = 1e9 + 7;
const ll inf = 1e18 + 77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, q;
ll t=0;
vector<pll> a[dim];
ll tin[dim];
ll deg[dim];
ll marked[dim];
ll dp[dim];
ll solve(ll v, ll p){
    ll mn=inf; // mn - мінімум на шляху до останнього незайманого
    vll can;
    ll ans=0;
    for(auto x: a[v]){
        if(x.fi!=p){
           ll nw=solve(x.fi, v);
           ans+=dp[x.fi];
           nw=min(nw, x.se);
           can.pb(nw);
        }
    }
    sort(can.begin(), can.end());
    ll sz=can.size();
    for(int i=0; i<sz-1; i++){
        ans+=can[i];// ок а якщо на шляху нікого немає? ==> їх mn=0
    }
    if(sz-1>=0)mn=min(mn, can[sz-1]);
    else{ mn=0; }
    if(marked[v]){ans+=mn; mn=inf;}
    dp[v]=ans;
  //  cout<<v<<" "<<dp[v]<<" "<<mn<<" "<<marked[v]<<endl;
    return mn;
}
int main() {
    cin>>n;
    for(int i=1; i<=n-1; i++){
        ll u, v, w;
        cin>>u>>v>>w;
        u++;
        v++;
        a[u].pb({v, w});
        a[v].pb({u, w});
    }

    ll root;
    cin>>q;
    while(q--){
        vll cur(5, 0);
        cin>>cur[0]>>cur[1]>>cur[2]>>cur[3]>>cur[4];
        for(auto x:cur){
            x++;
            marked[x]=1;
        }
        ll tmp=solve(1, 0);
        cout<<dp[1]<<endl;
        for(auto x:cur){
            marked[x]=0;
        }


    }
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 40
• Subtask 4: 0 / 30