| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 643558 | Kripton | The Potion of Great Power (CEOI20_potion) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int h[100001];
vector <pair <int,int>> v[100001];
vector <int> v1[100001];
bool cmp(int a,int b)
{
return h[a]<h[b];
}
int vec1[501],vec2[501];
int cnt1,cnt2;
bool ap[100001];
int main()
{
#ifdef HOME
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
#endif // HOME
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,d,u,q,i,a,b,zi,min1,j,x,y;
cin>>n>>d>>u>>q;
for(i=0; i<n; i++)
cin>>h[i];
for(i=1; i<=u; i++)
{
cin>>a>>b;
v[a].push_back({b,i});
v[b].push_back({a,i});
}
for(i=0; i<n; i++)
{
for(j=0; j<v[i].size(); j++)
{
if(!ap[v[i][j].first])
{
ap[v[i][j].first]=1;
v1[i].push_back(v[i][j].first);
}
}
for(j=0; j<v[i].size(); j++)
ap[v[i][j].first]=0;
sort(v1[i].begin(),v1[i].end(),cmp);
}
for(i=1; i<=q; i++)
{
min1=1e9;
cnt1=cnt2=0;
cin>>x>>y>>zi;
for(j=0; j<v[x].size(); j++)
{
if(v[x][j].second>zi)
break;
ap[v[x][j].first]^=1;
}
for(j=0; j<v1[x].size(); j++)
if(ap[v1[x][j]])
vec1[++cnt1]=h[v1[x][j]];
for(j=0; j<v1[x].size(); j++)
ap[v1[x][j]]=0;
for(j=0; j<v[y].size(); j++)
{
if(v[y][j].second>zi)
break;
ap[v[y][j].first]^=1;
}
for(j=0; j<v1[y].size(); j++)
if(ap[v1[y][j]])
vec2[++cnt2]=h[v1[y][j]];
for(j=0; j<v1[y].size(); j++)
ap[v1[y][j]]=0;
if(cnt1==0||cnt2==0)
cout<<min1<<endl;
else
{
int t=1;
for(int s=1; s<=cnt1; s++)
{
while(t<cnt2&&vec2[t]<vec1[s])
t++;
if(vec2[t]==vec1[s])
{
min1=0;
break;
}
if(t==1)
min1=min(min1,abs(vec2[t]-vec1[s]));
else
min1=min(min1,min(abs(vec2[t]-vec1[s]),abs(vec2[t-1]-vec1[s])));
}
cout<<min1<<endl;
}
}
return 0;
}