Submission #985159

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
9851592024-05-17 11:45:29GhettoRoad Closures (APIO21_roads)C++17
0 / 100
2079 ms20300 KiB
#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pii = pair<int, int>;
using pll = pair<lint, lint>;
const int MAX_N = 1e5 + 5;
int n;
vector<int> adj[MAX_N];
int n_inds, ind[MAX_N];
vector<int> children[MAX_N];
bool size_cmp(int u, int v) { return adj[u].size() > adj[v].size(); }
void dfs1(int u, int par = -1) {
n_inds++, ind[u] = n_inds;
for (int v : adj[u])
if (v != par) dfs1(v, u), children[u].push_back(v);
sort(children[u].begin(), children[u].end(), size_cmp);
}
vector<int> size_ord;
void precomp() {
dfs1(0, -1);
for (int u = 0; u < n; u++) size_ord.push_back(u);
sort(size_ord.begin(), size_ord.end(), size_cmp);
}
unordered_set<int> seen;
lint dp[MAX_N][2];
void dfs2(int u, int k) {
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

roads.cpp: In function 'void dfs2(int, int)':
roads.cpp:35:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |         if (adj[v].size() <= k) break;
      |             ~~~~~~~~~~~~~~^~~~
roads.cpp: In function 'lint solve_k(int)':
roads.cpp:52:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |         if (adj[u].size() <= k) break;
      |             ~~~~~~~~~~~~~~^~~~
#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...