이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |