oj.uz

Submission #342444

# Submission time Handle Problem Language Result Execution time Memory
342444 2021-01-02T06:40:48 Z urd05 The Potion of Great Power (CEOI20_potion) C++14
49 / 100
 3000 ms 47336 KB 
#include <bits/stdc++.h>
using namespace std;

int n,d;
int h[100000];
int a[200000];
int b[200000];
int u;
bool iscon0[100000];
bool iscon1[100000];
typedef pair<int,int> P;
P ind[100000];
set<int> s[100000];
typedef pair<int,int> P;
vector<P> ve[100000];
vector<int> ch0[100000];
vector<int> ch1[100000];
int zc[100000];
int oc[100000];
bool zeroone=true;

void init(int N, int D, int H[]) {
    n=N;
    d=D;
    for(int i=0;i<n;i++) {
        ind[i]=P(H[i],i);
        h[i]=H[i];
        s[i].clear();
        ve[i].clear();
        if (h[i]>1) {
            zeroone=false;
        }
    }
    sort(ind,ind+n);
}

void curseChanges(int U, int A[], int B[]) {
    u=U;
    for(int i=0;i<u;i++) {
        a[i]=A[i];
        b[i]=B[i];
        if (s[a[i]].find(b[i])==s[a[i]].end()) {
            if (h[b[i]]==0&&zc[a[i]]==0) {
                ch0[a[i]].push_back(i);
            }
            if (h[b[i]]==1&&oc[a[i]]==0) {
                ch1[a[i]].push_back(i);
            }
            s[a[i]].insert(b[i]);
            if (h[b[i]]==0) {
                zc[a[i]]++;
            }
            else {
                oc[a[i]]++;
            }
        }
        else {
            s[a[i]].erase(b[i]);
            if (h[b[i]]==0) {
                zc[a[i]]--;
            }
            else {
                oc[a[i]]--;
            }
            if (h[b[i]]==0&&zc[a[i]]==0) {
                ch0[a[i]].push_back(i);
            }
            if (h[b[i]]==1&&oc[a[i]]==0) {
                ch1[a[i]].push_back(i);
            }
        }
        if (s[b[i]].find(a[i])==s[b[i]].end()) {
            if (h[a[i]]==0&&zc[b[i]]==0) {
                ch0[b[i]].push_back(i);
            }
            if (h[a[i]]==1&&oc[b[i]]==0) {
                ch1[b[i]].push_back(i);
            }
            s[b[i]].insert(a[i]);
            if (h[a[i]]==0) {
                zc[b[i]]++;
            }
            else {
                oc[b[i]]++;
            }
        }
        else {
            s[b[i]].erase(a[i]);
            if (h[a[i]]==0) {
                zc[b[i]]--;
            }
            else {
                oc[b[i]]--;
            }
            if (h[a[i]]==0&&zc[b[i]]==0) {
                ch0[b[i]].push_back(i);
            }
            if (h[a[i]]==1&&oc[b[i]]==0) {
                ch1[b[i]].push_back(i);
            }
        }
    }
    for(int i=0;i<n;i++) {
        for(auto curr:s[i]) {
            ve[i].push_back(P(h[curr],i));
        }
        sort(ve[i].begin(),ve[i].end());
    }
}

int question2(int x, int y, int v) {
	memset(iscon0,0,sizeof(iscon0));
	memset(iscon1,0,sizeof(iscon1));
    for(int i=0;i<v;i++) {
        if (a[i]==x) {
            iscon0[b[i]]^=1;
        }
        else if (b[i]==x) {
            iscon0[a[i]]^=1;
        }
        if (a[i]==y) {
            iscon1[b[i]]^=1;
        }
        else if (b[i]==y) {
            iscon1[a[i]]^=1;
        }
    }
    int ret=1e9;
    vector<P> one;
    vector<P> two;
    for(int i=0;i<n;i++) {
        if (iscon0[ind[i].second]) {
            one.push_back(P(ind[i].first,0));
        }
    }
    for(int i=0;i<n;i++) {
        if (iscon1[ind[i].second]) {
            two.push_back(P(ind[i].first,1));
        }
    }
    vector<P> vec(one.size()+two.size());
    merge(one.begin(),one.end(),two.begin(),two.end(),vec.begin());
    for(int i=0;i+1<vec.size();i++) {
        if (vec[i].second!=vec[i+1].second) {
            ret=min(ret,vec[i+1].first-vec[i].first);
        }
    }
    return ret;
}

int question3(int x,int y,int v) {
    vector<P> vec(ve[x].size()+ve[y].size());
    merge(ve[x].begin(),ve[x].end(),ve[y].begin(),ve[y].end(),vec.begin());
    int ret=1e9;
    for(int i=0;i+1<vec.size();i++) {
        if (vec[i].second!=vec[i+1].second) {
            ret=min(ret,vec[i+1].first-vec[i].first);
        }
    }
    return ret;
}

int question4(int x,int y,int v) {
    bool xz=(lower_bound(ch0[x].begin(),ch0[x].end(),v)-ch0[x].begin())%2;
    bool xo=(lower_bound(ch1[x].begin(),ch1[x].end(),v)-ch1[x].begin())%2;
    bool yz=(lower_bound(ch0[y].begin(),ch0[y].end(),v)-ch0[y].begin())%2;
    bool yo=(lower_bound(ch1[y].begin(),ch1[y].end(),v)-ch1[y].begin())%2;
    if (xz&&yz) {
        return 0;
    }
    if (xo&&yo) {
        return 0;
    }
    if ((xz|xo)&&(yz|yo)) {
        return 1;
    }
    return 1e9;
}

int question(int x,int y,int v) {
    if (zeroone) {
        return question4(x,y,v);
    }
	if (u==v) {
		return question3(x,y,v);
	}
	else {
	    return question2(x,y,v);
	}
}

Compilation message

potion.cpp: In function 'int question2(int, int, int)':
potion.cpp:143:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for(int i=0;i+1<vec.size();i++) {
      |                 ~~~^~~~~~~~~~~
potion.cpp: In function 'int question3(int, int, int)':
potion.cpp:155:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for(int i=0;i+1<vec.size();i++) {
      |                 ~~~^~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12524 KB Output is correct
2 Correct 20 ms 12524 KB Output is correct
3 Correct 20 ms 12524 KB Output is correct
4 Correct 279 ms 14444 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 41664 KB Output is correct
2 Correct 382 ms 41708 KB Output is correct
3 Correct 156 ms 17048 KB Output is correct
4 Correct 561 ms 26804 KB Output is correct
5 Correct 475 ms 39148 KB Output is correct
6 Correct 751 ms 24716 KB Output is correct
7 Correct 324 ms 24812 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 47336 KB Output is correct
2 Correct 201 ms 19724 KB Output is correct
3 Correct 336 ms 28140 KB Output is correct
4 Correct 344 ms 28012 KB Output is correct
5 Correct 427 ms 46700 KB Output is correct
6 Correct 349 ms 28212 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1901 ms 13932 KB Output is correct
2 Correct 1968 ms 12804 KB Output is correct
3 Correct 2239 ms 12652 KB Output is correct
4 Correct 2624 ms 13292 KB Output is correct
5 Correct 2478 ms 13804 KB Output is correct
6 Correct 1195 ms 13676 KB Output is correct
7 Execution timed out 3089 ms 12908 KB Time limit exceeded

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12268 KB Output is correct
2 Correct 22 ms 12524 KB Output is correct
3 Correct 20 ms 12524 KB Output is correct
4 Correct 20 ms 12524 KB Output is correct
5 Correct 279 ms 14444 KB Output is correct
6 Correct 387 ms 41664 KB Output is correct
7 Correct 382 ms 41708 KB Output is correct
8 Correct 156 ms 17048 KB Output is correct
9 Correct 561 ms 26804 KB Output is correct
10 Correct 475 ms 39148 KB Output is correct
11 Correct 751 ms 24716 KB Output is correct
12 Correct 324 ms 24812 KB Output is correct
13 Correct 416 ms 47336 KB Output is correct
14 Correct 201 ms 19724 KB Output is correct
15 Correct 336 ms 28140 KB Output is correct
16 Correct 344 ms 28012 KB Output is correct
17 Correct 427 ms 46700 KB Output is correct
18 Correct 349 ms 28212 KB Output is correct
19 Correct 1901 ms 13932 KB Output is correct
20 Correct 1968 ms 12804 KB Output is correct
21 Correct 2239 ms 12652 KB Output is correct
22 Correct 2624 ms 13292 KB Output is correct
23 Correct 2478 ms 13804 KB Output is correct
24 Correct 1195 ms 13676 KB Output is correct
25 Execution timed out 3089 ms 12908 KB Time limit exceeded