이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
ifstream in("f.in");
ofstream out("f.out");
#define int long long
int bucket_size = 640;
int sqsize = 450;
int n,m,q,N;
vector<int>G[100005];
vector<pair<int,int>>g[200005];
pair<int,int>edges[100005];
vector<int>midedges[100005];
struct ura
{
int nrgold,nrsilver,x,y,idx;
};
bool cmp(ura A,ura B)
{
if (A.x / bucket_size != B.x / bucket_size)
return A.x < B.x;
return A.y < B.y;
}
ura v[100005];
int curpm;
pair<int,int> pm[400005];
bool viz[200005];
int valoare[200005];
int tin[200005],tout[200005];
int height[200005];
int tata[200005];
int rval[200005];
int raspuns[100005];
void traversal(int nod)
{
viz[nod] = true;
pm[++curpm] = {nod,valoare[nod]};
tin[nod] = curpm;
for (auto vecin : g[nod])
if (!viz[vecin.first])
{
height[vecin.first] = 1 + height[nod];
tata[vecin.first] = nod;
valoare[vecin.first] = vecin.second;
traversal(vecin.first);
}
pm[++curpm] = {nod,valoare[nod]};
tout[nod] = curpm;
}
void normalize_values()
{
map<int,int>mpnorma;
int posnorma = 0;
vector<int>vnorma;
for (int i = 1; i <= n; i++)
vnorma.push_back(valoare[i]);
sort(vnorma.begin(),vnorma.end());
for (int i = 0; i < vnorma.size(); i++)
if (!mpnorma[vnorma[i]])
mpnorma[vnorma[i]] = ++posnorma,rval[posnorma] = vnorma[i];
for (int i = 1; i <= n; i++)
valoare[i] = mpnorma[valoare[i]];
for (int i = 1; i <= 2 * n; i++)
pm[i].second = valoare[pm[i].first];
}
int lmo = 1,rmo = 0;
bool am[200005];
int fr[300005],sm[300005];
int frb[505],smb[505];
int catetot;
void upd(int x,int coef)
{
//out << pm[x].first << ' ' << coef << '\n';
catetot += coef;
int vl = pm[x].second,rvl = rval[vl];
fr[vl] += coef;
sm[vl] += coef * rvl;
frb[vl / sqsize] += coef;
smb[vl / sqsize] += coef * rvl;
}
void baga(int x,int coef)
{
//cout << x << ' ' << coef << '\n';
if ((am[pm[x].first] == false and coef == 1) or (am[pm[x].first] == true and coef == -1))
{
upd(x,coef);
}
else
{
upd(x,-coef);
}
if (am[pm[x].first] == true)
am[pm[x].first] = false;
else
am[pm[x].first] = true;
}
void ansquery(int pos)
{
int gold = v[pos].nrgold,silver = v[pos].nrsilver;
int catenice = 0;
for (int i = 0; i <= n / sqsize; i++)
{
if (silver >= smb[i])
{
silver -= smb[i];
catenice += frb[i];
}
else if (silver != 0)
{
for (int j = i * sqsize; j < (i + 1) * sqsize; j++)
{
if (silver >= sm[j])
{
silver -= sm[j];
catenice += fr[j];
}
else
{
catenice += silver / rval[j];
silver = 0;
}
}
}
else
{
if (i == 0)
catenice += fr[1];
}
}
gold -= (catetot - catenice);
if (gold < 0)
raspuns[v[pos].idx] = -1;
else
raspuns[v[pos].idx] = gold;
}
void mo()
{
for (int i = 1; i <= q; i++)
{
while (rmo < v[i].y)
{
rmo++;
baga(rmo,1);
}
while (lmo > v[i].x)
{
lmo--;
baga(lmo,1);
}
while (rmo > v[i].y)
{
baga(rmo,-1);
rmo--;
}
while (lmo < v[i].x)
{
baga(lmo,-1);
lmo++;
}
ansquery(i);
}
}
void buildg()
{
n = N + m;
int cur = N;
for (int i = 1; i < N; i++)
{
int x = edges[i].first,y = edges[i].second;
if (midedges[i].size() == 0)
{
g[x].push_back({y,0});
g[y].push_back({x,0});
}
else
{
cur++;
g[x].push_back({cur,midedges[i][0]});
g[cur].push_back({x,midedges[i][0]});
for (int j = 1; j < midedges[i].size(); j++)
{
cur++;
g[cur - 1].push_back({cur,midedges[i][j]});
g[cur].push_back({cur - 1,midedges[i][j]});
}
g[cur].push_back({y,0});
g[y].push_back({cur,0});
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> m >> q;
for (int i = 1; i < N; i++)
{
int x,y;
cin >> x >> y;
if (x > y)
swap(x,y);
G[x].push_back(y);
G[y].push_back(x);
edges[i] = {x,y};
}
for (int i = 1; i <= m; i++)
{
int p,c;
cin >> p >> c;
midedges[p].push_back(c);
}
buildg();
/*for (int i = 1; i <= n; i++)
{
out << g[i].size() << '\n';
for (int j = 0; j < g[i].size(); j++)
out << g[i][j].first << ' ' << g[i][j].second << '\n';
}*/
for (int i = 1; i <= q; i++)
cin >> v[i].x >> v[i].y >> v[i].nrgold >> v[i].nrsilver,v[i].idx = i;
traversal(1);
/*for (int i = 1; i <= 2 * n; i++)
{
out << pm[i].first << ' ' << pm[i].second << '\n';
}*/
for (int i = 1; i <= q; i++)
{
if (tin[v[i].x] > tin[v[i].y])
swap(v[i].x,v[i].y);
if (tout[v[i].x] > tout[v[i].y])
v[i].x = tin[v[i].x] + 1,v[i].y = tin[v[i].y];
else
v[i].x = tout[v[i].x],v[i].y = tin[v[i].y];
}
//out << '\n';
sort(v + 1,v + q + 1,cmp);
/*for (int i = 1; i <= q; i++)
out << v[i].x << ' ' << v[i].y << '\n';*/
normalize_values();
mo();
for (int i = 1; i <= q; i++)
cout << raspuns[i] << '\n';
return 0;
}
/**
daca am o taxa de c pe muchia x-y, pot crea un nod fictiv pe muchia x y, fie el z, a.i x z e muchia anterioara si z y e o muchie de cost c
bun, acum ca am query-uri pe liniarizare
e ceva de genul: pe interv [x y], cate pot lua cu suma <= z?
cand mut capetele in mo, bag sau scot elemente
3 tipuri de operatii acum:
-baga x
-scoate x
-cate elem pot avea cu suma <= z?
imi tin valorile alea normalizate (ca totusi)
si bag un sqrt decomp frumos
gasesc ultimul bucket din care pot lua tot
din urmatorul merg unul cate unul si iau ce pot
**/
컴파일 시 표준 에러 (stderr) 메시지
currencies.cpp: In function 'void normalize_values()':
currencies.cpp:67:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i = 0; i < vnorma.size(); i++)
| ~~^~~~~~~~~~~~~~~
currencies.cpp: In function 'void buildg()':
currencies.cpp:196:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for (int j = 1; j < midedges[i].size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~
# | 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... |