oj.uz

답안 #969268

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969268 2024-04-24T20:45:48 Z tset The Potion of Great Power (CEOI20_potion) C++14
21 / 100
 1279 ms 262144 KB 
#include<bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
const int INF = 1e9;

int nbElem, nbVoisinsMax, nbDays;
vector<int > alti;
const int SQRTDAY = 100;
vector<set<int > > save[SQRTDAY *200];
vector<set<int > > voisins;
vector<int > Us, Vs;
void init(int N, int D, int F[])
{
    nbElem = N;
    nbVoisinsMax = D;
    alti.resize(N);
    for(int i=0; i<SQRTDAY *2; i++)
    {
        save[i].resize(N);
    }
    voisins.resize(N);
    for(int i=0; i< N; i++)
    {
        alti[i] = F[i];
    }
}

void curseChanges(int U, int A[], int B[])
{
    nbDays = U;
    for(int iDay = 0; iDay < nbDays; iDay++)
    {
        if(iDay%SQRTDAY == 0)
        {
            save[iDay/SQRTDAY] = voisins;
        }
        int u = A[iDay];
        int v = B[iDay];
        if(voisins[u].find(v) != voisins[u].end())
        {
            voisins[u].erase(v);
            voisins[v].erase(u);
        }
        else
        {
            voisins[u].insert(v);
            voisins[v].insert(u);
        }
        Us.push_back(A[iDay]);
        Vs.push_back(B[iDay]);
    }
}

int question(int X, int Y, int V)
{
    V--;
    int day = V;
    set<int> vx, vy;
    int backupDate = day/SQRTDAY;
    vx = save[backupDate][X];
    vy = save[backupDate][Y];
    for(int dayRecover = backupDate*SQRTDAY; dayRecover<= day; dayRecover++)
    {
        int u = Us[dayRecover];
        int v = Vs[dayRecover];
        if(u == X)
        {
            if(vx.find(v) != vx.end())

                vx.erase(v);
            else
                vx.insert(v);
        }
        if(v == X)
        {
            if(vx.find(u) != vx.end())
                vx.erase(u);
            else
                vx.insert(u);
        }

        if(u == Y)
        {
            if(vy.find(v) != vy.end())
                vy.erase(v);
            else
                vy.insert(v);
        }
        if(v == Y)
        {
            if(vy.find(u) != vy.end())
                vy.erase(u);
            else
                vy.insert(u);
        }
        
    }
    int ans = INF;
    vector<pii > altis;
    for(int valX : vx)
    {
        altis.push_back({alti[valX], 0});
    }
    for(int valY: vy)
    {
        altis.push_back({alti[valY], 1});
    }
    sort(altis.begin(), altis.end());
    vector<int> lasts(2, -INF);
    for(pii altiAct : altis)
    {
        lasts[altiAct.second] =  altiAct.first;
        ans=  min(ans, abs(lasts[0] - lasts[1]));
    }
    if(ans == INF)
        return 1000000000;
    return ans;

}

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 856 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10672 KB Output is correct
2 Correct 6 ms 10840 KB Output is correct
3 Correct 6 ms 10840 KB Output is correct
4 Runtime error 89 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 87 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 86 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 143660 KB Output is correct
2 Correct 145 ms 100788 KB Output is correct
3 Correct 322 ms 97080 KB Output is correct
4 Correct 1185 ms 124616 KB Output is correct
5 Correct 1279 ms 137116 KB Output is correct
6 Correct 224 ms 56656 KB Output is correct
7 Correct 984 ms 102872 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 6 ms 10672 KB Output is correct
3 Correct 6 ms 10840 KB Output is correct
4 Correct 6 ms 10840 KB Output is correct
5 Runtime error 89 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -