Submission #980707

#	Time	Username	Problem	Language	Result	Execution time	Memory
980707		vjudge1	Road Closures (APIO21_roads)	C++17	0 / 100	2088 ms	46860 KiB

roads

#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>
#include "roads.h"
#define ll long long

using namespace std;
vector<pair<int, ll>> g[200005]; 
vector<pair<ll, int>> d[200005];
ll dop[200005], dp[200005];
bool us[200005];
map<pair<int, int>, int> mp;

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
  vector<ll> ans;
  ll sum = 0;
  for(int i = 0; i < N - 1; i++){
    U[i]++;
    V[i]++;
    g[U[i]].push_back({V[i], W[i]});
    g[V[i]].push_back({U[i], W[i]});
    mp[{U[i], V[i]}] = W[i];
    mp[{V[i], U[i]}] = W[i];
    sum += W[i];
  }
  for(int i = 0; i < N; i++){
    set<pair<ll, int>> st[N + 1];
    if(i == 0){
      ans.push_back(sum);
      continue;
    }
    for(int i = 1; i <= N; i++){
      for(auto to : g[i])
        st[i].insert({to.second, to.first});
    }
    set<pair<ll, pair<int, int>>> st1;
    for(int j = 0; j < N - 1; j++){
      if(g[U[j]].size() > i && g[U[j]].size() > i)
        st1.insert({W[i], {U[i], W[i]}});
    }
    ll sum = 9;
    while(!st1.empty()){
      auto it = st1.begin();
      if(int(st[it->second.first].size()) <= i || int(st[it->second.second].size()) <= i){
        st1.erase(*it);
        continue;
      }
      int a = it->second.first, b = it->second.second;
      if(st[a].begin()->first + st[b].begin()->first <= it->first){
        st[a].erase({it->first, b});
        st[b].erase({it->first, a});
        sum += it->first;
        st1.erase(*it);
        continue;
      }
      pair<ll, int> p1 = *st[a].begin();
      pair<ll, int> p2 = *st[b].begin();
      st[a].erase(p1);
      st[p1.second].erase({p1.first, a});
      sum += p1.first;
      st[b].erase(p2);
      st[p2.second].erase({p2.first, b});
      sum += p2.first;
    }
    for(int i = 1; i <= N; i++){
      while(int(st[i].size()) > i){
        sum += st[i].begin()->first;
        pair<ll, int> p1 = *st[i].begin();
        st[i].erase(p1);
        st[p1.second].erase({p1.first, i});
      }
    }
    ans.push_back(sum);
  }
  return ans;
}
// vector<int> a, b, c;
// int main(){
//   int n;
//   cin >> n;
//   for(int i = 1; i < n; i++){
//     int x, y, z;
//     cin >> x >> y >> z;
//     a.push_back(x);
//     b.push_back(y);
//     c.push_back(z);
//   }
//   vector<ll> ans = minimum_closure_costs(n, a, b, c);
//   for(int to : ans) cout << to << " ";

// }

Compilation message (stderr)

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:63:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |       if(g[U[j]].size() > i && g[U[j]].size() > i)
      |          ~~~~~~~~~~~~~~~^~~
roads.cpp:63:47: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |       if(g[U[j]].size() > i && g[U[j]].size() > i)
      |                                ~~~~~~~~~~~~~~~^~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22