| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 643558 | Kripton | The Potion of Great Power (CEOI20_potion) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}