Submission #1300227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300227		mduchello	Roadside Advertisements (NOI17_roadsideadverts)	C++20	70 / 100	308 ms	8136 KiB

roadsideadverts

#include<bits/stdc++.h>

using namespace std;

//=====================================================================================================================================

#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pii pair<int, int>
#define BIT(i, mask) ((mask >> (i)) & 1)
#define DAOBIT(i, mask) ((mask ^ (1 << i)))
#define OFFBIT(i, mask) ((mask & ~(1 << (i))))
#define ONBIT(i, mask) ((mask | (1 << (i))))
#define nmax 1000007

//=====================================================================================================================================

const int N = 1e6 + 7;
const ll mod = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll inf = 1e18;

bool check_sub2 = 1;

int n, q;
vector<pil> adj[N];
int ts[10];
int u, v;
ll w;
ll sum_w;
//=====================================================================================================================================

void fre(){
    freopen("TET.INP", "r", stdin);
    freopen("TET.out", "w", stdout);
}
ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b){
    return (a / gcd(a, b)) * b;
}

namespace sub2{
    ll d[N];
    void pre_sub2(int u, int p, ll w){
        d[u] = w;
        for(pil e : adj[u]){
            int v = e.fi;
            ll w2 = e.se;
            if(v == p) continue;
            pre_sub2(v, u, w + w2);
        }
    }
    void solve(){
        int root = 0;
        for(int i = 1; i <= n; i++) if(adj[i].size() == 1) root = i;
        pre_sub2(root, 0, 0);
        while(q--){
            for(int i = 1; i <= 5; i++) cin >> ts[i];
            for(int i = 1; i <= 5; i++) ts[i]++;
            ll ans = 0;
            for(int i = 1; i <= 5; i++){
                for(int j = 1; j <= 5; j++){
                    ans = max(ans, d[ts[j]] - d[ts[i]]);
//                    cout << ts[j] << ' ' << ts[i] << ' ' << d[ts[j]] - d[ts[i]] << '\n';
                }
            }
            cout << ans << '\n';
        }
    }
}

namespace sub3{
    int cnt[N];
    ll wtp[N];
    bool f[N];
    void dfs_sub3(int u, int p){
        if(f[u]) cnt[u]++;
        for(pil e : adj[u]){
            int v = e.fi;
            ll w2 = e.se;
            if(v == p) continue;
            dfs_sub3(v, u);
            wtp[v] = w2;
            cnt[u] += cnt[v];
        }
    }
    void solve(){
        while(q--){
            for(int i = 1; i <= 5; i++) cin >> ts[i];
            for(int i = 1; i <= 5; i++) ts[i]++;
            for(int i = 1; i <= 5; i++) f[ts[i]] = 1;
            ll ans = sum_w;
            dfs_sub3(1, 0);
            for(int i = 1; i <= n; i++){
                if(cnt[i] == 0 || cnt[i] == 5) ans -= wtp[i];
                cnt[i] = 0;
            }
            for(int i = 1; i <= 5; i++) f[ts[i]] = 0;
            cout << ans << '\n';
        }
    }
}


//=====================================================================================================================================

int main(){
    cin.tie(0)->sync_with_stdio(0);
    // fre();
    cin >> n;
    for(int i = 1; i < n; i++){
        cin >> u >> v >> w;
        u++;
        v++;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
        sum_w += w;
        check_sub2 &= (adj[u].size() <= 2);
        check_sub2 &= (adj[v].size() <= 2);
    }
    if(n == 5 && q == 1){
        cout << sum_w << '\n';
        return 0;
    }
    cin >> q;
    if(check_sub2){
        sub2 :: solve();
        return 0;
    }
    if(n <= 50000 && q <= 100){
        sub3 :: solve();
        return 0;
    }




    return 0;
}

Compilation message (stderr)

roadsideadverts.cpp: In function 'void fre()':
roadsideadverts.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen("TET.INP", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     freopen("TET.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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