Submission #597128

#	Time	Username	Problem	Language	Result	Execution time	Memory
597128		AlperenT	Werewolf (IOI18_werewolf)	C++17	0 / 100	425 ms	179948 KiB

werewolf

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

using namespace std;

const int N = 2e5 + 5;

struct DSU{
    int par[N];

    set<pair<int, int>> st[N];

    void reset(int n){
        for(int i = 0; i < n; i++) par[i] = i, st[i].clear();
    }

    int setfind(int a){
        if(par[a] == a) return a;
        else return par[a] = setfind(par[a]);
    }

    void setunion(int a, int b){
        a = setfind(a), b = setfind(b);

        if(a != b){
            if(b < a) swap(a, b);

            if(st[b].size() > st[a].size()) swap(st[a], st[b]);

            par[b] = par[a];

            for(auto p : st[b]) st[a].insert(p);

            st[b].clear();
        }
    }
};

DSU human_dsu, wolfdsu, curhuman;

vector<int> graph[N];

vector<pair<int, int>> humanstart[N], humanend[N], wolfstart[N];;

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();

    vector<int> ans(q, false);

    human_dsu.reset(n), wolfdsu.reset(n), curhuman.reset(n);

    for(int i = 0; i < m; i++){
        graph[x[i]].push_back(y[i]);
        graph[y[i]].push_back(x[i]);
    }

    for(int i = 0; i < q; i++) humanstart[s[i]].push_back({l[i], i});

    for(int i = 0; i < q; i++) wolfstart[e[i]].push_back({r[i], i});

    for(int v = n - 1; v >= 0; v--){
        for(auto p : humanstart[v]){
            human_dsu.st[human_dsu.setfind(v)].insert(p);
        }

        for(auto e : graph[v]){
            if(e > v){
                while(!human_dsu.st[human_dsu.setfind(e)].empty() && prev(human_dsu.st[human_dsu.setfind(e)].end())->first > v){
                    humanend[human_dsu.setfind(e)].push_back(*prev(human_dsu.st[human_dsu.setfind(e)].end()));
                    human_dsu.st[human_dsu.setfind(e)].erase(prev(human_dsu.st[human_dsu.setfind(e)].end()));
                }

                human_dsu.setunion(v, e);
            }
        }

        int vv = human_dsu.setfind(v);

        while(!human_dsu.st[vv].empty() && prev(human_dsu.st[vv].end())->first >= v){
            humanend[v].push_back(*prev(human_dsu.st[vv].end()));
            human_dsu.st[vv].erase(prev(human_dsu.st[vv].end()));
        }
    }

    for(int v = 0; v < n; v++){
        for(auto p : wolfstart[v]) wolfdsu.st[wolfdsu.setfind(v)].insert(p);

        while(!wolfdsu.st[wolfdsu.setfind(v)].empty() && wolfdsu.st[wolfdsu.setfind(v)].begin()->first < v){
            wolfdsu.st[wolfdsu.setfind(v)].erase(wolfdsu.st[wolfdsu.setfind(v)].begin());
        }

        for(auto p : humanend[v]) curhuman.st[curhuman.setfind(v)].insert(p);

        while(!wolfdsu.st[wolfdsu.setfind(v)].empty() && wolfdsu.st[wolfdsu.setfind(v)].begin()->first < v){
            wolfdsu.st[wolfdsu.setfind(v)].erase(wolfdsu.st[wolfdsu.setfind(v)].begin());
        }

        for(auto it = curhuman.st[curhuman.setfind(v)].begin(); it != curhuman.st[curhuman.setfind(v)].begin(); ){
            if(wolfdsu.st[wolfdsu.setfind(v)].find({r[it->second], it->second}) != wolfdsu.st[wolfdsu.setfind(v)].end()){
                ans[it->second] = true;

                wolfdsu.st[wolfdsu.setfind(v)].erase({r[it->second], it->second});
                it = curhuman.st[curhuman.setfind(v)].erase(it);
            }
            else it++;
        }

        for(auto e : graph[v]){
            if(e < v){
                while(!wolfdsu.st[wolfdsu.setfind(e)].empty() && wolfdsu.st[wolfdsu.setfind(e)].begin()->first < v){
                    wolfdsu.st[wolfdsu.setfind(e)].erase(wolfdsu.st[wolfdsu.setfind(e)].begin());
                }

                if(curhuman.st[curhuman.setfind(e)].size() < wolfdsu.st[wolfdsu.setfind(v)].size()){
                    for(auto it = curhuman.st[curhuman.setfind(e)].begin(); it != curhuman.st[curhuman.setfind(e)].end(); ){
                        if(wolfdsu.st[wolfdsu.setfind(v)].find({r[it->second], it->second}) != wolfdsu.st[wolfdsu.setfind(v)].end()){
                            ans[it->second] = true;

                            wolfdsu.st[wolfdsu.setfind(v)].erase({r[it->second], it->second});
                            it = curhuman.st[curhuman.setfind(e)].erase(it);
                        }
                        else it++;
                    }
                }
                else{
                    for(auto it = wolfdsu.st[wolfdsu.setfind(v)].begin(); it != wolfdsu.st[wolfdsu.setfind(v)].end(); ){
                        if(curhuman.st[curhuman.setfind(e)].find({l[it->second], it->second}) != curhuman.st[curhuman.setfind(e)].end()){
                            ans[it->second] = true;

                            curhuman.st[curhuman.setfind(e)].erase({l[it->second], it->second});
                            it = wolfdsu.st[wolfdsu.setfind(v)].erase(it);
                        }
                        else it++;
                    }
                }

                if(curhuman.st[curhuman.setfind(v)].size() < wolfdsu.st[wolfdsu.setfind(e)].size()){
                    for(auto it = curhuman.st[curhuman.setfind(v)].begin(); it != curhuman.st[curhuman.setfind(v)].end(); ){
                        if(wolfdsu.st[wolfdsu.setfind(e)].find({r[it->second], it->second}) != wolfdsu.st[wolfdsu.setfind(e)].end()){
                            ans[it->second] = true;

                            wolfdsu.st[wolfdsu.setfind(e)].erase({r[it->second], it->second});
                            it = curhuman.st[curhuman.setfind(e)].erase(it);
                        }
                        else it++;
                    }
                }
                else{
                    for(auto it = wolfdsu.st[wolfdsu.setfind(e)].begin(); it != wolfdsu.st[wolfdsu.setfind(e)].end(); ){
                        if(curhuman.st[curhuman.setfind(v)].find({l[it->second], it->second}) != curhuman.st[curhuman.setfind(v)].end()){
                            ans[it->second] = true;

                            curhuman.st[curhuman.setfind(v)].erase({l[it->second], it->second});
                            it = wolfdsu.st[wolfdsu.setfind(e)].erase(it);
                        }
                        else it++;
                    }
                }

                wolfdsu.setunion(v, e);

                curhuman.setunion(v, e);
            }

        }
    }

    return ans;
}

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