제출 #1087980

#제출 시각아이디문제언어결과실행 시간메모리
1087980Valaki2봉쇄 시간 (IOI23_closing)C++17
8 / 100
93 ms35156 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define mp make_pair #define pii pair<int, int> #define fi first #define se second const int maxn = 2e5; struct edge { int to, wei; }; int ans; int n, x, y, k; vector<pii > g[1 + maxn]; int d[2][1 + maxn]; bool done[2][1 + maxn]; void dfs(int cur, int idx, int par) { for(pii nei : g[cur]) { if(nei.fi != par) { d[idx][nei.fi] = d[idx][cur] + nei.se; dfs(nei.fi, idx, cur); } } } struct item { int val; int pos; int type; bool operator < (const item & other) const { return val > other.val; } }; int sum, cur_ans; priority_queue<item> q; void push_for(item cur) { for(pii nei : g[cur.pos]) { if(!done[cur.type][nei.fi]) { q.push({d[cur.type][nei.fi], nei.fi, cur.type}); } } } bool eval(item cur) { if(cur.val > k - sum) { return false; } sum += cur.val; cur_ans++; done[cur.type][cur.pos] = true; push_for(cur); return true; } void solve() { dfs(x, 0, -1); dfs(y, 1, -1); q.push({0, x, 0}); q.push({0, y, 1}); sum = 0, cur_ans = 0; while(!q.empty()) { item cur = q.top(); q.pop(); bool res = eval(cur); if(!res) { break; } } ans = cur_ans; } void reset() { ans = 0; for(int i = 1; i <= n; i++) { g[i].clear(); d[0][i] = d[1][i] = 0; done[0][i] = done[1][i] = false; } sum = 0, cur_ans = 0; while(!q.empty()) { q.pop(); } // } signed max_score(signed N, signed X, signed Y, int K, vector<signed> U, vector<signed> V, vector<signed> W) { reset(); n = N, x = X, y = Y, k = K; x++; y++; for(int i = 0; i < n - 1; i++) { int a = U[i], b = V[i], c = W[i]; a++; b++; g[a].pb(mp(b, c)); g[b].pb(mp(a, c)); } solve(); return ans; }
#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...