Submission #205295

#	Time	Username	Problem	Language	Result	Execution time	Memory
205295		medk	Werewolf (IOI18_werewolf)	C++14	0 / 100	596 ms	65904 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(200001);
vector<bool> vis(200001);
vector<int> ln,pos(200001);

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r)
{
    int m=x.size(), q=s.size();
    for(int i=0;i<m;i++) g[x[i]].pb(y[i]), g[y[i]].pb(x[i]);
    int leaf;
    for(int i=0;i<n;i++) if((int)g[i].size()==1) {leaf=i; break;}
    while((int)ln.size()<n)
    {
        pos[leaf]=(int)ln.size();
        ln.pb(leaf);
        vis[leaf]=1;
        for(int v:g[leaf])
        {
            if(vis[v]) continue;
            leaf=v;
        }
    }
    vector<pair<int,int>> L,R;
    for(int i=0;i<q;i++) L.pb({-l[i],i}), R.pb({r[i],i});
    sort(L.begin(),L.end());
    sort(R.begin(),R.end());
    vector<int> lftmost(q);
    int ptr=n-1;
    set<pair<int,int>> st;
    for(int i=0;i<q;i++)
    {
        while(ptr>=-L[i].x)
        {
            int ps=pos[ptr];
            auto it=st.upper_bound({ps,ps});
            pair<int,int> p={ps,ps};
            if(it!=st.end())
                if((*it).x==ps+1) p.y=(*it).y, st.erase(it);
            if((int)st.size())
                if((*prev(it)).y==ps-1) p.x=(*prev(it)).x, st.erase(prev(it));
            st.insert(p);
            ptr--;
        }
        auto it2=prev(st.lower_bound({s[L[i].y]+1,-1}));
        lftmost[L[i].y]=(*it2).x;
    }
    ptr=0;
    st.clear();
    vector<int> ans(q);
    for(int i=0;i<q;i++)
    {
        while(ptr<=R[i].x)
        {
            int ps=pos[ptr];
            auto it=st.upper_bound({ps,ps});
            pair<int,int> p={ps,ps};
            if(it!=st.end())
                if((*it).x==ps+1) p.y=(*it).y, st.erase(it);
            if((int)st.size())
                if((*prev(it)).y==ps-1) p.x=(*prev(it)).x, st.erase(prev(it));
            st.insert(p);
            ptr++;
        }
        auto it2=prev(st.lower_bound({e[R[i].y]+1,-1}));
        ans[R[i].y]=((*it2).y>=lftmost[R[i].y]);
    }
    return ans;
}

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