Submission #858026

#	Time	Username	Problem	Language	Result	Execution time	Memory
858026		sofijavelkovska	The Potion of Great Power (CEOI20_potion)	C++14	0 / 100	162 ms	172976 KiB

potion

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5, MAXU=2e5, INF=1e9, ROOT=1000;

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

pair<int, int> adj[MAXU/ROOT+5][MAXN];
bool type[MAXU];

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];
    pair<int, int> currentadj[MAXN]={{0, 0}};
    set<pair<int, int> > edges;
    for (int i=0; i<u; i++)
    {
        if (i%ROOT==0)
        {
            for (int j=0; j<n; j++)
                adj[i/ROOT][j]=currentadj[j];
        }
        if (i==u)
            break;
        int x=a[i], y=b[i];
        if (y<x)
            swap(x, y);
        if (!edges.count({x, y}))
        {
            edges.insert({x, y});
            type[i]=true;
            if (h[x]==0)
                currentadj[y].first=currentadj[y].first+1;
            else
                currentadj[y].second=currentadj[y].second+1;
            if (h[y]==0)
                currentadj[x].first=currentadj[x].first+1;
            else
                currentadj[x].second=currentadj[x].second+1;
        }
        else
        {
            edges.erase({x, y});
            type[i]=false;
            if (h[x]==0)
                currentadj[y].first=currentadj[y].first-1;
            else
                currentadj[y].second=currentadj[y].second-1;
            if (h[y]==0)
                currentadj[x].first=currentadj[x].first-1;
            else
                currentadj[x].second=currentadj[x].second-1;
        }

    }

    return;
}

int question(int x, int y, int v)
{
    pair<int, int> xtrust, ytrust;
    xtrust=adj[v/ROOT][x];
    ytrust=adj[v/ROOT][y];
    for (int i=v-v%ROOT; i<v; i++)
    {
        if (a[i]==x)
        {
            if (type[i])
            {
                if (h[b[i]]==0)
                    xtrust.first=xtrust.first+1;
                else
                    xtrust.second=xtrust.second+1;
            }
            else
            {
                if (h[b[i]]==0)
                    xtrust.first=xtrust.first-1;
                else
                    xtrust.second=xtrust.second-1;
            }
        }
        if (b[i]==x)
        {
            if (type[i])
            {
                if (h[a[i]]==0)
                    xtrust.first=xtrust.first+1;
                else
                    xtrust.second=xtrust.second+1;
            }
            else
            {
                if (h[a[i]]==0)
                    xtrust.first=xtrust.first-1;
                else
                    xtrust.second=xtrust.second-1;
            }
        }
        if (a[i]==y)
        {
            if (type[i])
            {
                if (h[b[i]]==0)
                    ytrust.first=ytrust.first+1;
                else
                    ytrust.second=ytrust.second+1;
            }
            else
            {
                if (h[b[i]]==0)
                    ytrust.first=ytrust.first-1;
                else
                    ytrust.second=ytrust.second-1;
            }
        }
        if (b[i]==y)
        {
            if (type[i])
            {
                if (h[a[i]]==0)
                    ytrust.first=ytrust.first+1;
                else
                    ytrust.second=ytrust.second+1;
            }
            else
            {
                if (h[a[i]]==0)
                    ytrust.first=ytrust.first-1;
                else
                    ytrust.second=ytrust.second-1;
            }
        }
    }
    if (xtrust==make_pair(0, 0) || ytrust==make_pair(0, 0))
        return INF;
    if (xtrust.first>0 && ytrust.first>0)
        return 0;
    if (xtrust.second>0 && ytrust.second>0)
        return 0;

    return 1;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 30