Submission #1128598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128598		guagua0407	Werewolf (IOI18_werewolf)	C++20	100 / 100	2083 ms	161076 KiB

werewolf

//#include "grader.cpp"
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    const int mxn=2e5+5;
    const int inf=1e9;
    vector<int> adj[mxn];
    set<pair<int,pair<int,int>>> S[mxn];
    vector<pair<int,int>> R[mxn];
}

struct DSU{
    vector<int> e;
    vector<vector<int>> B;
    DSU(int n){
        e=vector<int>(n,-1);
        B.resize(n);
        for(int i=0;i<n;i++){
            B[i].push_back(i);
            R[i].push_back({-1,i});
        }
    }
    int find(int x){
        return (e[x]<0?x:e[x]=find(e[x]));
    }
    bool unite(int a,int b,int t){
        a=find(a);
        b=find(b);
        if(a==b) return false;
        if(e[a]>e[b]) swap(a,b);
        e[a]+=e[b];
        e[b]=a;
        for(auto v:B[b]){
            R[v].push_back({t,a});
            B[a].push_back(v);
        }
        vector<int>().swap(B[b]);
        return true;
    }
};

struct DSU2{
    vector<int> e;
    DSU2(int n){
        e=vector<int>(n,-1);
    }
    int find(int x){
        return (e[x]<0?x:e[x]=find(e[x]));
    }
    bool unite(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b) return false;
        if(e[a]>e[b]) swap(a,b);
        e[a]+=e[b];
        e[b]=a;
        for(auto v:S[b]){
            S[a].insert(v);
            auto it=S[a].find(v);
            it=next(it);
            while(it!=S[a].end() and (*it).f==v.f and (*it).s<=v.s) it=S[a].erase(it);
        }
        set<pair<int,pair<int,int>>>().swap(S[b]);
        return true;
    }
    bool query(int a,int b,int tr){
        a=find(a);
        /*cout<<a<<' '<<b<<'\n';
        for(auto v:S[a]){
            cout<<v.f<<' '<<v.s.f<<' '<<v.s.s<<'\n';
        }
        cout<<'\n';*/
        int sz=(int)R[b].size();
        for(int i=0;i<sz-1;i++){
            int l=R[b][i].f;
            int r=R[b][i+1].f-1;
            int v=R[b][i].s;
            if(l>tr) break;
            r=min(r,tr);
            if(l>r) continue;
            //cout<<v<<' '<<l<<' '<<r<<'\n';
            auto L=S[a].lower_bound({v,{l,-1}});
            if(L!=S[a].begin()){
                L=prev(L);
                if((*L).f==v and (*L).s.s>=l) return true;
                L=next(L);
            }
            if(L!=S[a].end()){
                if((*L).f==v and (*L).s.f<=r) return true;
            }
        }
        return false;
    }
};

std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,std::vector<int> SS, std::vector<int> E,std::vector<int> L, std::vector<int> RR) {
    int m=(int)X.size();
    for(int i=0;i<m;i++){
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    DSU dsu(n);
    for(int i=0;i<n;i++){
        for(auto v:adj[i]){
            if(v<i){
                dsu.unite(i,v,i);
            }
        }
    }
    int q=(int)L.size();
    vector<vector<int>> qs(n);
    vector<int> ans(q);
    for(int i=0;i<q;i++){
        qs[L[i]].push_back(i);
    }
    for(int i=0;i<n;i++){
        R[i].push_back(make_pair(n,dsu.find(i)));
    }
    for(int i=0;i<n;i++){
        int sz=(int)R[i].size();
        for(int j=0;j<sz-1;j++){
            if(R[i][j].f<R[i][j+1].f) S[i].insert({R[i][j].s,{R[i][j].f,R[i][j+1].f-1}});
        }
    }
    DSU2 dsu2(n);
    for(int i=n-1;i>=0;i--){
        //cout<<"diaob "<<i<<'\n';
        for(auto v:adj[i]){
            if(v>i){
                dsu2.unite(i,v);
            }
        }
        for(auto v:qs[i]){
            ans[v]=dsu2.query(SS[v],E[v],RR[v]);
        }
    }
    return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

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