Submission #1121212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121212		PagodePaiva	Beads and wires (APIO14_beads)	C++17	0 / 100	2 ms	336 KiB

beads

#include<bits/stdc++.h>

using namespace std;

const int N = 11;
int res = 0;
set <pair <int, int>> g[N];
int markarestas[N], markvertices[N];
int ans = 0;
int n;

void backtracking(){
  ans = max(ans, res);
  for(int i = 1;i <= n;i++){
    if(markvertices[i] == 1) continue;
    markvertices[i] = 1;
    vector <array <int, 4>> arestas;
    for(auto [x, w] : g[i]){
      for(auto [y, w2] : g[i]){
        if(x == y) continue;
        arestas.push_back({x, y, w, w2});
      }
    }
    for(auto [x, y, w,w2] : arestas){
      g[i].erase({x, w});
      g[i].erase({y, w2});
      g[x].erase({i, w});
      g[y].erase({i, w2});
      res += w+w2;
      backtracking();
      res -= w+w2;
      g[i].insert({x, w});
      g[i].insert({y, w2});
      g[x].insert({i, w});
      g[y].insert({i, w2});
    }
    markvertices[i] = 0;
  }
}

int main(){
  cin >> n;
  for(int i = 1;i < n;i++){
    int a, b, w;
    cin >> a >> b >> w;
    g[a].insert({b, w});
    g[b].insert({a, w});
  }
  backtracking();
  cout << ans << '\n';
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43