Submission #1225446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225446		i_love_spring	Tug of War (BOI15_tug)	C++20	0 / 100	5 ms	5440 KiB

tug

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int N = 60005;
int n,k,w1[N],w2[N],s[N],visited[N];
multiset<ar<int,2>>g[N];
ll d = 0;
void dfs(int u) {
  visited[u] = 1;
  for (auto [v, cost] : g[u]) {
    g[v].erase(g[v].find({u,-cost}));
    if (!visited[v]) {
      d += cost;
      dfs(v);
    }
  }
  g[u].clear();
}
void solve() {
  cin >> n >> k;
  memset(visited,0,n * 2 + 5);
  for (int i = 1; i <= n * 2;i++) cin >> w1[i] >> w2[i] >> s[i];
  // making graph , let's nodes of this graph denotes places, and edges denotes people
  for (int i = 1; i <= n * 2;i++) g[w1[i]].insert({w2[i] + n,s[i]}),g[w2[i] + n].insert({w1[i],-s[i]});
  for (int i = 1; i <= n * 2;i++) {
    if (g[i].empty()) { // if nobody wants this place 
      cout << "NO";
      return;
    }
  }
  queue<int> q;
  for (int i = 1; i <= n * 2;i++) {
    if (g[i].size() == 1) q.push(i); // if there's only one person who wants this place
  }
  d = 0;
  while (!q.empty()) {
    int u = q.front(); // u is place not person
    q.pop();
    if (g[u].size() == 0) {
      cout << "NO";
      return;
    }
    for (auto[v,cost] : g[u]) {
      d += cost;
      // cost will be opposite
      g[v].erase(g[v].find({u,-cost}));
      if (g[v].size() == 1) q.push(v);
    }
  }
  vector<ll>vals;
  if (d) vals.push_back(abs(d));
  for (int i = 1; i <= n * 2;i++) {
    // we know that every single node belong to exactly one componenent that is full of cycle, so we just go dfs , and remove this edges
    if (!visited[i] && !g[i].empty()) {
      d = 0;
      g[i].erase(g[i].begin()); // this edge is redundant 
      dfs(i);
      if (d) vals.push_back(abs(d));
    }
  }
  cout << "YES\n";
  return;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
} 

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 23
• Subtask 4: 0 / 29