Submission #987546

#	Time	Username	Problem	Language	Result	Execution time	Memory
987546		cig32	Designated Cities (JOI19_designated_cities)	C++17	6 / 100	2061 ms	28756 KiB

designated_cities

#include "bits/stdc++.h"
#define int long long
using namespace std;
const int MAXN = 4e5 + 10;
int n;
vector<pair<int,int>> adj[MAXN];
int ans[MAXN];
set<pair<pair<int,int>, int> > st;
void dfs0(int node, int prv) {
  for(auto x: adj[node]) {
    if(x.first != prv) {
      st.insert({{node, x.first}, x.second});
      dfs0(x.first, node);
    }
  }
}
int all;
void solve(int tc) {
  cin >> n;
  for(int i=0; i<=n; i++) ans[i] = 1e18;
  for(int u=1; u<n; u++) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    all += c + d;
    a--, b--;
    adj[a].push_back({b, d});
    adj[b].push_back({a, c});
  }
  for(int i=0; i<(1<<n); i++) {
    st.clear();
    for(int j=0; j<n; j++) {
      if(i & (1<<j)) {
        dfs0(j, -1);
      }
    }
    int done = 0;
    for(auto x: st) done += x.second;
    int pc=__builtin_popcount(i);
    ans[pc] = min(ans[pc], all - done);
  }
  int q;
  cin >> q;
  while(q--) {
    int e;
    cin >> e;
    cout << ans[e] << '\n';
  }
  
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t=1; //cin>>t;
  for(int i=1; i<=t; i++) solve(i);
}
/*
g++ T2441.cpp -std=c++17 -O2 -o T2441
./T2441 < input.txt
*/

• Subtask 1: 6 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44