oj.uz

Submission #858035

# Submission time Handle Problem Language Result Execution time Memory
858035 2023-10-07T10:46:16 Z sofijavelkovska The Potion of Great Power (CEOI20_potion) C++14
31 / 100
 3000 ms 34272 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5, INF=1e9;

int n, d, u;
vector<int> h, a, b;

vector<int> adj[MAXN];

void init(int N, int D, int H[])
{
    n=N;
    d=D;
    h.resize(n);
    for (int i=0; i<n; i++)
        h[i]=H[i];

    return;
}

void curseChanges(int U, int A[], int B[])
{
    u=U;
    a.resize(u);
    b.resize(u);
    for (int i=0; i<u; i++)
        a[i]=A[i];
    for (int i=0; i<u; i++)
        b[i]=B[i];
    set<int> currentadj[n];
    for (int i=0; i<u; i++)
    {
        if (!currentadj[a[i]].count(b[i]))
        {
            currentadj[a[i]].insert(b[i]);
            currentadj[b[i]].insert(a[i]);
        }
        else
        {
            currentadj[a[i]].erase(b[i]);
            currentadj[b[i]].erase(a[i]);
        }
    }
    for (int i=0; i<n; i++)
    {
        for (auto t : currentadj[i])
            adj[i].push_back(h[t]);
        sort(adj[i].begin(), adj[i].end());
    }

    return;
}

int question(int x, int y, int v)
{
    vector<int> vx, vy;
    if (v==u)
    {
        vx=adj[x];
        vy=adj[y];
    }
    else
    {
        set<int> xtrust, ytrust;
        for (int i=0; i<v; i++)
        {
            if (a[i]==x)
            {
                if (!xtrust.count(b[i]))
                    xtrust.insert(b[i]);
                else
                    xtrust.erase(b[i]);
            }
            if (b[i]==x)
            {
                if (!xtrust.count(a[i]))
                    xtrust.insert(a[i]);
                else
                    xtrust.erase(a[i]);
            }
            if (a[i]==y)
            {
                if (!ytrust.count(b[i]))
                    ytrust.insert(b[i]);
                else
                    ytrust.erase(b[i]);
            }
            if (b[i]==y)
            {
                if (!ytrust.count(a[i]))
                    ytrust.insert(a[i]);
                else
                    ytrust.erase(a[i]);
            }
        }
        for (auto t : xtrust)
            vx.push_back(h[t]);
        for (auto t : ytrust)
            vy.push_back(h[t]);
        sort(vx.begin(), vx.end());
        sort(vy.begin(), vy.end());
    }
    if (vx.empty() || vy.empty())
        return INF;
    int mind=INF;
    int j=0;
    for (int i=0; i<vx.size(); i++)
    {
        while (j<vy.size() && vx[i]>vy[j])
            j=j+1;
        if (j<vy.size())
            mind=min(mind, vy[j]-vx[i]);
        if (j-1>=0)
            mind=min(mind, vx[i]-vy[j-1]);
    }

    return mind;
}

Compilation message

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for (int i=0; i<vx.size(); i++)
      |                   ~^~~~~~~~~~
potion.cpp:110:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         while (j<vy.size() && vx[i]>vy[j])
      |                ~^~~~~~~~~~
potion.cpp:112:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         if (j<vy.size())
      |             ~^~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2904 KB Output is correct
2 Correct 4 ms 2904 KB Output is correct
3 Correct 3 ms 2904 KB Output is correct
4 Correct 17 ms 8972 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 34060 KB Output is correct
2 Correct 190 ms 34272 KB Output is correct
3 Correct 86 ms 11952 KB Output is correct
4 Correct 275 ms 16368 KB Output is correct
5 Correct 235 ms 27624 KB Output is correct
6 Correct 319 ms 18776 KB Output is correct
7 Correct 135 ms 19008 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 33944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 4696 KB Output is correct
2 Correct 788 ms 3672 KB Output is correct
3 Execution timed out 3069 ms 3416 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 4 ms 2904 KB Output is correct
3 Correct 4 ms 2904 KB Output is correct
4 Correct 3 ms 2904 KB Output is correct
5 Correct 17 ms 8972 KB Output is correct
6 Correct 195 ms 34060 KB Output is correct
7 Correct 190 ms 34272 KB Output is correct
8 Correct 86 ms 11952 KB Output is correct
9 Correct 275 ms 16368 KB Output is correct
10 Correct 235 ms 27624 KB Output is correct
11 Correct 319 ms 18776 KB Output is correct
12 Correct 135 ms 19008 KB Output is correct
13 Execution timed out 3060 ms 33944 KB Time limit exceeded
14 Halted 0 ms 0 KB -