oj.uz

Submission #643561

# Submission time Handle Problem Language Result Execution time Memory
643561 2022-09-22T12:47:53 Z Kripton The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 1827 ms 16952 KB 
#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 n,d;
void init(int N,int D,int H[])
{
    n=N;
    d=D;
    for(int i=0; i<n; i++)
        h[i]=H[i];
}
void curseChanges(int U,int A[],int B[])
{
    for(int i=0; i<U; i++)
    {
        v[A[i]].push_back({B[i],i+1});
        v[B[i]].push_back({A[i],i+1});
    }
    for(int i=0; i<n; i++)
    {
        for(int 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(int j=0; j<v[i].size(); j++)
            ap[v[i][j].first]=0;
        sort(v1[i].begin(),v1[i].end(),cmp);
    }
}
int question(int x,int y,int zi)
{
    int min1=1e9,i,j;
    int cnt1=cnt2=0;
    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)
        return min1;
    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])));
        }
        return min1;
    }
}

Compilation message

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(int j=0; j<v[i].size(); j++)
      |                      ~^~~~~~~~~~~~
potion.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int j=0; j<v[i].size(); j++)
      |                      ~^~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(j=0; j<v[x].size(); j++)
      |              ~^~~~~~~~~~~~
potion.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(j=0; j<v1[x].size(); j++)
      |              ~^~~~~~~~~~~~~
potion.cpp:56:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(j=0; j<v1[x].size(); j++)
      |              ~^~~~~~~~~~~~~
potion.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(j=0; j<v[y].size(); j++)
      |              ~^~~~~~~~~~~~
potion.cpp:64:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(j=0; j<v1[y].size(); j++)
      |              ~^~~~~~~~~~~~~
potion.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(j=0; j<v1[y].size(); j++)
      |              ~^~~~~~~~~~~~~
potion.cpp:45:18: warning: unused variable 'i' [-Wunused-variable]
   45 |     int min1=1e9,i,j;
      |                  ^

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5072 KB Output is correct
2 Correct 4 ms 5072 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 16 ms 5956 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 16952 KB Output is correct
2 Correct 155 ms 16904 KB Output is correct
3 Correct 1206 ms 11144 KB Output is correct
4 Correct 498 ms 12676 KB Output is correct
5 Correct 149 ms 14120 KB Output is correct
6 Correct 1363 ms 15652 KB Output is correct
7 Correct 270 ms 16120 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 16800 KB Output is correct
2 Correct 1402 ms 13264 KB Output is correct
3 Correct 524 ms 15692 KB Output is correct
4 Correct 939 ms 15628 KB Output is correct
5 Correct 187 ms 16776 KB Output is correct
6 Correct 1049 ms 15756 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5712 KB Output is correct
2 Correct 56 ms 5444 KB Output is correct
3 Correct 155 ms 5344 KB Output is correct
4 Correct 367 ms 5712 KB Output is correct
5 Correct 320 ms 5712 KB Output is correct
6 Correct 51 ms 5368 KB Output is correct
7 Correct 555 ms 5456 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 4 ms 5072 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 16 ms 5956 KB Output is correct
6 Correct 159 ms 16952 KB Output is correct
7 Correct 155 ms 16904 KB Output is correct
8 Correct 1206 ms 11144 KB Output is correct
9 Correct 498 ms 12676 KB Output is correct
10 Correct 149 ms 14120 KB Output is correct
11 Correct 1363 ms 15652 KB Output is correct
12 Correct 270 ms 16120 KB Output is correct
13 Correct 140 ms 16800 KB Output is correct
14 Correct 1402 ms 13264 KB Output is correct
15 Correct 524 ms 15692 KB Output is correct
16 Correct 939 ms 15628 KB Output is correct
17 Correct 187 ms 16776 KB Output is correct
18 Correct 1049 ms 15756 KB Output is correct
19 Correct 30 ms 5712 KB Output is correct
20 Correct 56 ms 5444 KB Output is correct
21 Correct 155 ms 5344 KB Output is correct
22 Correct 367 ms 5712 KB Output is correct
23 Correct 320 ms 5712 KB Output is correct
24 Correct 51 ms 5368 KB Output is correct
25 Correct 555 ms 5456 KB Output is correct
26 Correct 454 ms 13672 KB Output is correct
27 Correct 616 ms 15768 KB Output is correct
28 Correct 609 ms 16584 KB Output is correct
29 Correct 437 ms 12744 KB Output is correct
30 Correct 1222 ms 15696 KB Output is correct
31 Correct 1827 ms 13320 KB Output is correct
32 Correct 1111 ms 15648 KB Output is correct