Submission #122962

#	Time	Username	Problem	Language	Result	Execution time	Memory
122962		medk	Werewolf (IOI18_werewolf)	C++14	0 / 100	607 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;

vector<vector<int>> g;
vector<int> ln;
vector<pair<pair<int,int>,int>> q,q2;
vector<int> ord;
vector<bool> is1, is2;
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), 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 s=S[i], e=E[i], l=L[i], r=R[i];
        q.pb({{r,e},i});
        q2.pb({{l,s},i});
    }
    sort(q.begin(),q.end());
    sort(q2.begin(),q2.end(),greater<pair<pair<int,int>,int>>());
    int k=0;
    for(int i=0;i<n;i++)
    {
        int j=ord[i];
        is1[j]=1;
        while(k<Q && q[k].x.x==i)
        {
            int id=ord[q[k].x.y];
            int lft=id;
            while(lft>0)
            {
                if(is1[lft-1]) lft--;
                else break;
            }
            int rgt=id;
            while(rgt<n-1)
            {
                if(is1[rgt+1]) rgt++;
                else break;
            }
            rng1[q[k].y]={lft,rgt};
            k++;
        }
    }
    k=0;
    for(int i=n-1;i>=0;i--)
    {
        int j=ord[i];
        is2[j]=1;
        while(k<Q && q2[k].x.x==i)
        {
            int id=ord[q[k].x.y];
            int lft=id;
            while(lft>0)
            {
                if(is2[lft-1]) lft--;
                else break;
            }
            int rgt=id;
            while(rgt<n-1)
            {
                if(is2[rgt+1]) rgt++;
                else break;
            }
            rng2[q2[k].y]={lft,rgt};
            k++;
        }
    }
    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
        {ret.pb(1);}
    }
    return ret;
}
/*
int main()
{
    vector<int> ans=check_validity(5,{0,1,2,3},{3,4,4,2},{},{},{},{});
    for(int x:ans) cout<<x<<" ";
}
*/

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