| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 343483 | leinad2 | The Potion of Great Power (CEOI20_potion) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
void init(int N, int D, int F[]);
void curseChanges(int U, int A[], int B[]);
int question(int X, int Y, int V);
int main() {
int N, D, U, Q;
scanf("%d %d %d %d", &N, &D, &U, &Q);
int *F = new int[N];
for (int i=0; i<N; i++)
scanf("%d", &F[i]);
init(N, D, F);
int *A = new int[U], *B = new int[U];
for (int i=0; i<U; i++) {
scanf("%d %d", &A[i], &B[i]);
}
curseChanges(U, A, B);
bool correct = true;
for (int i=0; i<Q; i++) {
int X,Y,V,CorrectAnswer;
std::cin >> X >> Y >> V >> CorrectAnswer;
int YourAnswer = question(X,Y,V);
if (YourAnswer != CorrectAnswer) {
std::cout << "WA! Question: " << i
<< " (X=" << X << ", Y=" << Y << ", V=" << V << ") "
<< "Your answer: " << YourAnswer
<< " Correct Answer: " << CorrectAnswer << std::endl;
correct = false;
} else {
std::cerr << YourAnswer << " - OK" << std::endl;
}
}
if (correct) {
std::cout << "Correct." << std::endl;
} else std::cout << "Incorrect." << std::endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n, d, H[10010], i, j, u, A[10010], B[10010], b, x, a;
set<int>adj[10010][105], F[10010], X;
set<int>::iterator it, it2;
void init(int N, int D, int HH[])
{
n=N;
d=D;
for(i=0;i<n;i++)H[i]=HH[i];
}
void curseChanges(int U, int C[], int D[])
{
u=U;
for(i=0;i++<u;)A[i]=C[i-1],B[i]=D[i-1];
b=(int)round(sqrt(u));
for(i=0;i++<u;)
{
if(F[B[i]].find(A[i])==F[B[i]].end())
{
F[A[i]].insert(B[i]);
F[B[i]].insert(A[i]);
}
else
{
F[A[i]].erase(B[i]);
F[B[i]].erase(A[i]);
}
if(i%b==0)
{
for(j=0;j<n;j++)
{
for(it=F[j].begin();it!=F[j].end();it++)
{
adj[j][i/b].insert(*it);
}
}
}
}
}
int question(int s, int e, int v)
{
x=v/b;
for(i=b*x+1;i<=v;i++)
{
if(adj[B[i]][x].find(A[i])==adj[B[i]][x].end())
{
adj[A[i]][x].insert(B[i]);
adj[B[i]][x].insert(A[i]);
}
else
{
adj[A[i]][x].erase(B[i]);
adj[B[i]][x].erase(A[i]);
}
}
int ans=1e9;
if(adj[s][x].size()==0||adj[e][x].size()==0)
{
goto w;
}
X.clear();
for(it=adj[s][x].begin();it!=adj[s][x].end();it++)
{
X.insert(H[*it]);
}
for(it=adj[e][x].begin();it!=adj[e][x].end();it++)
{
it2=X.lower_bound(H[*it]);
if(it2==X.end())it2--;
ans=min(ans, abs(H[*it]-*it2));
if(it2==X.begin())continue;
it2--;
ans=min(ans, abs(H[*it]-*it2));
}
w:;
for(i=v;i>b*x;i--)
{
if(adj[B[i]][x].find(A[i])==adj[B[i]][x].end())
{
adj[A[i]][x].insert(B[i]);
adj[B[i]][x].insert(A[i]);
}
else
{
adj[A[i]][x].erase(B[i]);
adj[B[i]][x].erase(A[i]);
}
}
return ans;
}