oj.uz

Submission #987546

# Submission time Handle Problem Language Result Execution time Memory
987546 2024-05-23T02:10:54 Z cig32 Designated Cities (JOI19_designated_cities) C++17
6 / 100
 2000 ms 28756 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Correct 236 ms 10740 KB Output is correct
3 Correct 228 ms 10740 KB Output is correct
4 Correct 216 ms 10744 KB Output is correct
5 Correct 229 ms 10588 KB Output is correct
6 Correct 237 ms 10584 KB Output is correct
7 Correct 222 ms 10748 KB Output is correct
8 Correct 231 ms 10736 KB Output is correct
9 Correct 207 ms 10584 KB Output is correct
10 Correct 220 ms 10736 KB Output is correct
11 Correct 180 ms 10740 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Incorrect 122 ms 28756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10588 KB Output is correct
2 Incorrect 109 ms 28668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Correct 236 ms 10740 KB Output is correct
3 Correct 228 ms 10740 KB Output is correct
4 Correct 216 ms 10744 KB Output is correct
5 Correct 229 ms 10588 KB Output is correct
6 Correct 237 ms 10584 KB Output is correct
7 Correct 222 ms 10748 KB Output is correct
8 Correct 231 ms 10736 KB Output is correct
9 Correct 207 ms 10584 KB Output is correct
10 Correct 220 ms 10736 KB Output is correct
11 Correct 180 ms 10740 KB Output is correct
12 Correct 4 ms 10584 KB Output is correct
13 Execution timed out 2061 ms 11100 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Incorrect 122 ms 28756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Correct 236 ms 10740 KB Output is correct
3 Correct 228 ms 10740 KB Output is correct
4 Correct 216 ms 10744 KB Output is correct
5 Correct 229 ms 10588 KB Output is correct
6 Correct 237 ms 10584 KB Output is correct
7 Correct 222 ms 10748 KB Output is correct
8 Correct 231 ms 10736 KB Output is correct
9 Correct 207 ms 10584 KB Output is correct
10 Correct 220 ms 10736 KB Output is correct
11 Correct 180 ms 10740 KB Output is correct
12 Correct 3 ms 10584 KB Output is correct
13 Incorrect 122 ms 28756 KB Output isn't correct
14 Halted 0 ms 0 KB -