Submission #122937

#	Time	Username	Problem	Language	Result	Execution time	Memory
122937		medk	Werewolf (IOI18_werewolf)	C++14	0 / 100	562 ms	524292 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define x first
#define y second

using namespace std;

struct query
{
    int e,s,l,r;
};
vector<vector<int>> g;
vector<int> ln;
vector<pair<int,query>> q,q2;
vector<pair<int,int>> lrng, rrng;
vector<int> ord;
vector<bool> is1, is2;
vector<pair<int,int>> par1,par2;
vector<pair<int,int>> rng1,rng2;

void makeline(int v, int par)
{
    ord[v]=int(ln.size());
    ln.pb(v);
    for(int x:g[v])
        if(x!=par) makeline(x,v);
}
vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
    vector<int> ret;
    int m=X.size(), Q=S.size();
    g.resize(n);
    ord.resize(n);
    unordered_set<int> elim;
    for(int i=0;i<n;++i) is1.pb(0), is2.pb(0), par1.pb({i,i}), par2.pb({i,i}), elim.insert(i);
    for(int i=0;i<m;i++)
    {
        int x=X[i], y=Y[i];
        g[x].pb(y);
        g[y].pb(x);
        if(g[x].size()==2) elim.erase(x);
        if(g[y].size()==2) elim.erase(y);
    }
    makeline(*elim.begin(),-1);
    for(int i=0;i<Q;i++)
    {
        rng1.pb({-1,-1}), rng2.pb({-1,-1});
        int a=S[i], b=E[i], c=L[i], d=R[i];
        q.pb({i,query{a,b,c,d}});
        q2.pb({i,query{a,b,c,d}});
    }
    sort(q.begin(),q.end(),[ ](const pair<int,query>& left, const pair<int,query>& right){return left.y.r < right.y.r;});
    sort(q2.begin(),q2.end(),[ ](const pair<int,query>& left, const pair<int,query>& right){return left.y.l > right.y.l;});
    int k=0;
    for(int i=0;i<n;i++)
    {
        int j=ord[i];
        is1[j]=1;
        if(j>0)
        {
            if(is1[j-1])
            {
                int id=j-1;
                while(par1[id].x!=id) id=par1[id].x;
                par1[j].x=id;
                id=j;
                while(par1[id].y!=id) id=par1[id].y;
                par1[j-1].y=id;
            }
        }
        if(j<n-1)
        {
            if(is1[j+1])
            {
                int id=j;
                while(par1[id].x!=id) id=par1[id].x;
                par1[j+1].x=id;
                id=j+1;
                while(par1[id].y!=id) id=par1[id].y;
                par1[j].y=id;
            }
        }
        while(k<Q && q[k].y.r==i)
        {
            int id=ord[q[k].y.s];
            int lft=par1[id].x;
            while(par1[lft].x!=lft) lft=par1[lft].x;
            int rgt=par1[id].y;
            while(par1[rgt].y!=rgt) rgt=par1[rgt].y;
            rng1[q[k].x]={lft,rgt};
            k++;
        }
    }
    k=0;
    for(int i=n-1;i>=0;i--)
    {
        int j=ord[i];
        is2[j]=1;
        if(j>0)
        {
            if(is2[j-1])
            {
                int id=j-1;
                while(par2[id].x!=id) id=par2[id].x;
                par2[j].x=id;
                id=j;
                while(par2[id].y!=id) id=par2[id].y;
                par2[j-1].y=id;
            }
        }
        if(j<n-1)
        {
            if(is2[j+1])
            {
                int id=j;
                while(par2[id].x!=id) id=par2[id].x;
                par2[j+1].x=id;
                id=j+1;
                while(par2[id].y!=id) id=par2[id].y;
                par2[j].y=id;
            }
        }
        while(k<Q && q2[k].y.l==i)
        {
            int id=ord[q2[k].y.e];
            int lft=par2[id].x;
            while(par2[lft].x!=lft) lft=par2[lft].x;
            int rgt=par2[id].y;
            while(par2[rgt].y!=rgt) rgt=par2[rgt].y;
            rng2[q2[k].x]={lft,rgt};
            k++;
        }
    }
    sort(q.begin(),q.end(), [ ](const pair<int,query>& left, const pair<int,query>& right){return left.x < right.x;});
    for(int i=0;i<Q;i++)
    {
        int l1=rng1[i].x, r1=rng1[i].y, l2=rng2[i].x, r2=rng2[i].y;
        if(l2>r1 || l1>r2) ret.pb(0);
        else
        {
            int l=max(l1,l2), r=min(r1,r2);
            bool flag=0;
            for(int k=min(l,r);k<=max(l,r);k++)
            {
                if(ln[k]!=q[i].y.e && ln[k]!=q[i].y.s)
                {
                    flag=1; break;
                }
            }
            if(flag) ret.pb(1);
            else ret.pb(0);
        }
    }
    return ret;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51