Submission #1074912

#TimeUsernameProblemLanguageResultExecution timeMemory
1074912bleahbleahClosing Time (IOI23_closing)C++17
0 / 100
174 ms59404 KiB
#include "closing.h" #include <vector> #include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; #define sz(x) ((int)(x).size()) using pii = pair<int,int>; const int nmax = 2e5 + 5; ll dx[nmax], dy[nmax]; int p[nmax]; vector<pii> g[nmax]; void filld(int node, int f, ll *d) { p[node] = f; for(auto [x, c] : g[node]) { if(x == f) continue; d[x] = d[node] + c; filld(x, node, d); } return; } int separate(int N, ll S) { vector<pii> s; for(int i = 0; i < N; i++) { s.emplace_back(i, 1); s.emplace_back(i, 2); } sort(all(s), [&](auto a, auto b) { a.first = (a.second == 1? dx[a.first] : dy[a.first]); b.first = (b.second == 1? dx[b.first] : dy[b.first]); return a.first < b.first; }); vector<int> occ(N, 0); int cnt = 0; for(auto [x, t] : s) { if(occ[x]) continue; x = (t == 1? dx[x] : dy[x]); if(S < x) break; S -= x; occ[x] = 1; cnt++; } return cnt; } int max_score(int N, int X, int Y, long long S, std::vector<int> U, std::vector<int> V, std::vector<int> W) { for(int i = 0; i <= N; i++) g[i].clear(); for(int i = 0; i < sz(U); i++) { g[U[i]].emplace_back(V[i], W[i]); g[V[i]].emplace_back(U[i], W[i]); } filld(X, X, dx); filld(Y, Y, dy); int opt1 = separate(N, S); return opt1; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...