Submission #434198

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
4341982021-06-20 17:54:42dqhungdlRoad Closures (APIO21_roads)C++17
24 / 100
2089 ms20192 KiB
#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int MAX=1e5+5;
const long long INF=1e18;
vector<long long> f0,f1; // f0: do not need to close parent edge, f1: force to close parent edge (f0[u] >= f1[u])
vector<ii> g[MAX];
void dfs(int u,int p,int atMost) {
long long sum=0,minSum=0;
for(ii edge:g[u]) {
int v=edge.first,w=edge.second;
if(v==p)
continue;
dfs(v,u,atMost);
sum+=f0[v];
minSum+=min(f0[v],f1[v]+w);
}
int eraseNum=(int)g[u].size()-atMost;
if(eraseNum<=0) {
f0[u]=f1[u]=minSum;
return;
}
vector<long long> gaps;
for(ii edge:g[u]) {
int v=edge.first,w=edge.second;
if(v==p)
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0;i<gaps.size();i++) {
      |              ~^~~~~~~~~~~~
#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...