Submission #848404

#	Time	Username	Problem	Language	Result	Execution time	Memory
848404		truc12a2cvp	봉쇄 시간 (IOI23_closing)	C++17	8 / 100	116 ms	32064 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> II;
const int N = 2e5 + 30, logN = 22;
const int MOD[2] = {998244353, 1000000007};
const int block = 20;
const ll inf  = 2e9;
const ll INF = 1e18;
#define ms(s, n) memset(s, n, sizeof(s))
#define sz(a) (int) ((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
#define point II
#define X first
#define Y second
inline ll sqr(int x) {return x * 1ll * x;}
inline int fpow(ll n, ll k, int p) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
inline void addmod(int& a, int val, int p) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p) {return (ll) a * b % p;}

vector<II> g[N];
vector<ll> op;

void dfs(int u, int p, ll dist){
       op.push_back(dist);
       for(auto x : g[u]){
              int v = x.first, w = x.second;
              if(v == p) continue;
              dfs(v, u, dist + w);
       }
}

int max_score(int n, int x, int y, long long k,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
       for(int i = 0; i < n; i ++) g[i].clear();
       op.clear();
       for(int i = 0; i < n - 1; i ++){
              g[U[i]].push_back(II(V[i], W[i]));
              g[V[i]].push_back(II(U[i], W[i]));
       }

       dfs(x, 0, 0);
       dfs(y, 0, 0);
       sort(op.begin(), op.end());
       for(int i = 0; i < (int)op.size(); i ++){
                     if(k < op[i]) return i;
                     k -= op[i];
       }
       return op.size();
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17