제출 #1116608

#제출 시각아이디문제언어결과실행 시간메모리
1116608hqminhuwuTwo Currencies (JOI23_currencies)C++14
0 / 100
30 ms36432 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef long double ld; typedef vector <int> vi; typedef pair <ll,ll> pll; typedef pair <int,int> pii; typedef pair <int,pii> piii; #define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a) #define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);) #define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a) #define st first #define nd second #define pb push_back #define mp make_pair #define all(x) begin(x),end(x) #define mask(i) (1LL << (i)) #define bit(x, i) (((x) >> (i)) & 1) #define bp __builtin_popcountll #define file "test" template<class X, class Y> bool minz(X &x, const Y &y) { if (x > y) { x = y; return true; } return false; } template<class X, class Y> bool maxz(X &x, const Y &y) { if (x < y) { x = y; return true; } return false; } const int N = 5e5 + 5; const ll oo = (ll) 1e16; const ll mod = 1e9 + 7; // 998244353; int n, m, q, u, v, p[N], c[N], x[N], s[N], t[N], ed[N]; ll y[N]; vector <int> tax[N], tmp, a[N]; namespace sub1 { bool dfs (int u, int p, int z){ if (u == z){ return 1; } for (int i : a[u]){ int v = ed[i] ^ u; if (v == p) continue; if (dfs(v, u, z)){ for (int w : tax[i]){ tmp.pb(w); } return 1; } } return 0; } void solve(){ forr (i, 1, q){ tmp.clear(); dfs(s[i], s[i], t[i]); sort(all(tmp)); int ans = -1, zz = 0; if (x[i] >= tmp.size()){ ans = x[i] - tmp.size(); } for (int v : tmp){ y[i] -= v; zz++; if (y[i] < 0) break; if (x[i] >= tmp.size() - zz){ ans = x[i] - (tmp.size() - zz); } } cout << ans << "\n"; } } } struct BIT{ ll bit[N]; void add (int u, ll val){ if (u <= 0) u = 1; for (; u <= n; u += u & -u){ bit[u] += val; } } void add (int l, int r, ll val){ add(l, val); add(r + 1, -val); } ll get (int u){ ll res = 0; for (; u; u -= u & -u){ res += bit[u]; } return res; } } bit1, bit2; namespace uwu { int tin[N], tout[N], cnt, dep[N], up[20][N], g[N], low[N], high[N], id[N], dir[N]; ll gd[N], sv[N], numgd[N], numsv[N], ans[N]; vector <int> qq[N]; void dfs (int u, int p){ tin[u] = ++cnt; for (int i : a[u]){ int v = ed[i] ^ u; if (v == p) continue; dir[i] = v; dep[v] = dep[u] + 1; up[0][v] = u; forr (i, 1, 17){ up[i][v] = up[i - 1][up[i - 1][v]]; } gd[v] = gd[u]; sv[v] = sv[u]; for (int w : tax[i]){ gd[v]++; sv[v] += w; } dfs(v, u); } tout[u] = cnt; } int lca (int u, int v){ if (dep[u] < dep[v]) swap(u, v); int k = dep[u] - dep[v]; ford (i, 17, 0) if (bit(i, k)){ u = up[i][u]; } if (u == v) swap(u, v); ford (i, 17, 0) if (up[i][u] != up[i][v]){ u = up[i][u]; v = up[i][v]; } return up[0][u]; } void solve(){ forr (i, 1, m){ id[i] = i; } sort(id + 1, id + 1 + m, [&](int &u, int &v){return c[u] < c[v];}); dfs(1, 1); forr (i, 1, q){ low[i] = 0; high[i] = m; g[i] = lca(s[i], t[i]); numsv[i] = sv[s[i]] + sv[t[i]] - sv[g[i]] - sv[up[0][g[i]]]; numgd[i] = gd[s[i]] + gd[t[i]] - gd[g[i]] - gd[up[0][g[i]]]; } int flag = 1; while (flag){ flag = 0; forr (i, 1, q){ if (low[i] != high[i]){ flag = 1; int mid = (low[i] + high[i] + 1) >> 1; qq[mid].pb(i); } } forr (i, 0, m){ int u = dir[p[i]]; // cout << u << " " << tin[u] << " " << tout[u] << endl; if (i){ bit2.add(tin[u], tout[u], c[id[i]]); } for (int j : qq[i]){ ll tmp = bit2.get(tin[s[j]]) + bit2.get(tin[t[j]]) - bit2.get(tin[g[j]]) - bit2.get(tin[up[0][g[j]]]); if (tmp <= y[j]){ low[j] = i; } else { high[j] = i - 1; } } qq[i].clear(); } forr (i, 1, n){ bit2.bit[i] = 0; } } forr (i, 1, q){ qq[low[i]].pb(i); } forr (i, 0, m){ int u = dir[p[i]]; if (i){ bit2.add(tin[u], tout[u], 1); } for (int j : qq[i]){ ll tmp = bit2.get(tin[s[j]]) + bit2.get(tin[t[j]]) - bit2.get(tin[g[j]]) - bit2.get(tin[up[0][g[j]]]); ans[j] = tmp; } qq[i].clear(); } forr (i, 1 , q){ x[i] -= numgd[i] - ans[i]; cout << (x[i] >= 0 ? x[i] : -1) << "\n"; } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef kaguya freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); #endif cin >> n >> m >> q; forf (i, 1, n){ cin >> u >> v; a[u].pb(i); a[v].pb(i); ed[i] = u ^ v; } forr (i, 1, m){ cin >> p[i] >> c[i]; } forr (i, 1, m){ tax[p[i]].pb(c[i]); } forr (i, 1, q){ cin >> s[i] >> t[i] >> x[i] >> y[i]; } // if (n <= 2000 && m <= 2000 && q <= 2000){ // sub1::solve(); // } else { uwu::solve(); } return 0; } /* */

컴파일 시 표준 에러 (stderr) 메시지

currencies.cpp: In function 'void sub1::solve()':
currencies.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             if (x[i] >= tmp.size()){
      |                 ~~~~~^~~~~~~~~~~~~
currencies.cpp:82:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |                 if (x[i] >= tmp.size() - zz){
      |                     ~~~~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...