Submission #597128

# Submission time Handle Problem Language Result Execution time Memory
597128 2022-07-15T14:28:47 Z AlperenT Werewolf (IOI18_werewolf) C++17
0 / 100
425 ms 179948 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 95628 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 95628 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 425 ms 179948 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 95628 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -