Submission #415335

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
4153352021-05-31 22:10:15ja_kingyRoad Closures (APIO21_roads)C++14
100 / 100
385 ms40076 KiB
#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int mxN = 1e5;
ll sm, par[mxN], is_root[mxN], dp[mxN][2], done[mxN], par_cost[mxN];
list<int> order;
vector<pii> adj[mxN];
vector<ll> ans;
struct dp_val {
ll v, dp0, dp1;
bool operator < (dp_val b) const {
ll da = dp1 - dp0, db = b.dp1 - b.dp0;
if (da != db) return da > db;
return v < b.v;
}
};
set<dp_val> bestk[mxN], extra[mxN];
void dfs(int u, int p, int pc) {
par[u] = p;
par_cost[u] = pc;
for (pii v: adj[u]) if (v.first != p) {
dfs(v.first, u, v.second);
}
order.push_back(u);
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

roads.cpp: In function 'void check_k(int, int)':
roads.cpp:34:25: warning: comparison of integer expressions of different signedness: 'std::set<dp_val>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     if (bestk[u].size() < k && extra[u].size()) {
      |         ~~~~~~~~~~~~~~~~^~~
roads.cpp:41:25: warning: comparison of integer expressions of different signedness: 'std::set<dp_val>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |     if (bestk[u].size() > k) {
      |         ~~~~~~~~~~~~~~~~^~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:104:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |             if (adj[u].size() == k) {
      |                 ~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...