Submission #849145

#	Time	Username	Problem	Language	Result	Execution time	Memory
849145		Tenis0206	Robots (APIO13_robots)	C++11	0 / 100	2 ms	9048 KiB

robots

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 1e5;
const int Mod = 1e9 + 7;

int n,q;

vector<int> G[nmax + 5];

int add[nmax + 5];

bool sw[nmax + 5];

int put[nmax + 5];

vector<int> l[nmax + 5];

int r[nmax + 5];
int rez, nr_grup;

struct dsu
{
    int t[nmax + 5], rang[nmax + 5];
    stack<pair<int,int> > st;
    dsu()
    {
        for(int i=1;i<=nmax;i++)
        {
            t[i] = i;
            rang[i] = 1;
        }
    }
    int reprezentant(int x)
    {
        if(t[x]==x)
        {
            return x;
        }
        return reprezentant(t[x]);
    }
    void uneste(int x, int y)
    {
        x = reprezentant(x);
        y = reprezentant(y);
        st.push({x,y});
        if(x==y)
        {
            return;
        }
        if(rang[x] < rang[y])
        {
            swap(x,y);
        }

        rez -= (put[rang[x]] + put[rang[y]]) % Mod;
        rez += Mod;
        rez %= Mod;

        t[y] = x;
        rang[x] += rang[y];

        rez += put[rang[x]];
        rez %= Mod;

        --nr_grup;
    }
    void undo()
    {
        int x = st.top().first;
        int y = st.top().second;
        st.pop();
        if(x==y)
        {
            return;
        }
        if(t[x]==y)
        {
            swap(x,y);
        }

        rez -= put[rang[x]];
        rez += Mod;
        rez %= Mod;

        t[y] = y;
        rang[x] -= rang[y];

        rez += (put[rang[x]] + put[rang[y]]) % Mod;
        rez %= Mod;

        ++nr_grup;
    }
}d;

void Add(int nod)
{
    sw[nod] = true;
    rez += 2;
    rez %= Mod;
    ++nr_grup;
    for(auto it : G[nod])
    {
        if(sw[it])
        {
            d.uneste(nod,it);
        }
    }
}

void Remove(int nod)
{
    for(auto it : G[nod])
    {
        if(sw[it])
        {
            d.undo();
        }
    }
    --nr_grup;
    rez -= 2;
    rez += Mod;
    rez %= Mod;
    sw[nod] = false;
}

void solve(int nod, int a, int b)
{
    for(auto it : l[nod])
    {
        Add(it);
    }
    if(a==b)
    {
        r[a] = (rez - nr_grup + Mod) % Mod;
        for(auto it : l[nod])
        {
            Remove(it);
        }
        return;
    }
    int mij = (a + b) >> 1;
    solve(nod*2,a,mij);
    solve(nod*2+1,mij+1,b);
    for(auto it : l[nod])
    {
        Remove(it);
    }
}

void update(int nod_gr, int ua, int ub, int nod, int a, int b)
{
    if(ua<=a && ub>=b)
    {
        l[nod].push_back(nod_gr);
        return;
    }
    int mij = (a + b) >> 1;
    if(ua<=mij)
    {
        update(nod_gr,ua,ub,nod*2,a,mij);
    }
    if(ub>mij)
    {
        update(nod_gr,ua,ub,nod*2+1,mij+1,b);
    }
}

signed main()
{
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    cin>>n>>q;
    put[0] = 1;
    for(int i=1;i<=n;i++)
    {
        put[i] = 2LL * put[i - 1] % Mod;
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        int val;
        cin>>val;
        if(val==0)
        {
            add[i] = 0;
        }
        else
        {
            add[i] = -1;
        }
    }
    for(int i=1;i<=q;i++)
    {
        int nod;
        cin>>nod;
        if(add[nod]==-1)
        {
            add[nod] = i;
        }
        else
        {
            update(nod,add[nod],i-1,1,0,q);
            add[nod] = -1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(add[i]!=-1)
        {
            update(i,add[i],n,1,0,q);
        }
    }
    solve(1,0,q);
    for(int i=0;i<=q;i++)
    {
        cout<<r[i]<<'\n';
    }
    return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:173:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |     freopen("nr.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:174:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |     freopen("nr.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40