Submission #296764

#	Time	Username	Problem	Language	Result	Execution time	Memory
296764		eohomegrownapps	Werewolf (IOI18_werewolf)	C++14	49 / 100	4083 ms	87404 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adjlist;

int n,m,q;

struct UFDS{
    vector<int> parent;
    vector<vector<int>> adjlist;
    vector<int> eulertour;

    UFDS(int n){
        parent.resize(n);
        adjlist.resize(n);
        for (int i = 0; i<n; i++){
            parent[i]=i;
        }
    }

    int root(int x){
        if (parent[x]==x){
            return x;
        }
        return root(parent[x]);
    }

    void connect(int a, int b){
        //cout<<"connect "<<a<<' '<<b<<endl;
        // connect b to a
        int rb = root(b);
        if (rb==a){return;}
        parent[rb]=a;
        adjlist[a].push_back(rb);
    }

    void geneulertour(int node){
        //cout<<"gen "<<node<<endl;
        eulertour.push_back(node);
        for (int i : adjlist[node]){
            geneulertour(i);
            eulertour.push_back(node);
        }
        if (adjlist[node].size()==0){
            eulertour.push_back(node);
        }
    }
};

void getranges(vector<int> &seq, bool increasing, vector<int> &queries, 
               vector<int> &limits, vector<int> &lvals, vector<int> &rvals){
    vector<vector<int>> val2ind(n);
    for (int i = 0; i<seq.size(); i++){
        val2ind[seq[i]].push_back(i);
    }
    vector<int> inds(q);
    for (int i = 0; i<q; i++){
        inds[i]=i;
    }
    if (increasing){
        sort(inds.begin(),inds.end(),[&limits](int a, int b){return limits[a]<limits[b];});
    } else {
        sort(inds.begin(),inds.end(),[&limits](int a, int b){return limits[a]>limits[b];});
    }
    set<int> insertedpoints;
    insertedpoints.insert(-1);
    insertedpoints.insert(seq.size());
    int prevval = increasing?0:n-1;
    for (int i = 0; i<q; i++){
        //cout<<"limit: "<<limits[inds[i]]<<'\n';
        while (prevval!=limits[inds[i]]){
            for (int v : val2ind[prevval]){
                //cout<<"insert "<<v<<'\n';
                insertedpoints.insert(v);
            }
            prevval+=increasing?1:-1;
        }
        auto lb = insertedpoints.lower_bound(val2ind[queries[inds[i]]][0]);
        //cout<<"lower: "<<*lb<<'\n';
        //cout<<"prev: "<<*(prev(lb))<<'\n';
        lvals[inds[i]]=*(prev(lb))+1;
        rvals[inds[i]]=*lb-1;
        //cout<<inds[i]<<'\n';
        //cout<<lvals[inds[i]]<<' '<<rvals[inds[i]]<<'\n';
    }
}

void display(vector<int> &v){
    for (int i : v){
        cout<<i<<' ';
    }cout<<'\n';
}

struct FenwickTree{
    //vector<int> fenwick;
    int fenwick[1000000];
    int n;
    FenwickTree(int _n){
        n=_n;
        //fenwick.resize(n+1);
    }

    void update(int ind){
        //cout<<"update "<<ind<<'\n';
        ind++;
        while (ind<=n){
            fenwick[ind]++;
            ind+=ind&(-ind);
        }
    }

    int qsum(int ind){
        ind++;
        if (ind==0){return 0;}
        int ans = 0;
        while (ind>0){
            ans+=fenwick[ind];
            ind-=ind&(-ind);
        }
        return ans;
    }

    int query(int a, int b){
        //cout<<"query "<<a<<' '<<b<<'\n';
        return qsum(b)-qsum(a-1);
    }
};

std::vector<int> check_validity(int N, std::vector<int> x, std::vector<int> y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    n=N;
    m=x.size();
    q=S.size();
    adjlist.resize(n);
    for (int i = 0; i<m; i++){
        adjlist[x[i]].push_back(y[i]);
        adjlist[y[i]].push_back(x[i]);
    }

    UFDS ue(n);
    for (int i = 1; i<n; i++){
        for (int j : adjlist[i]){
            if (j>i){continue;}
            ue.connect(i,j);
        }
    }
    ue.geneulertour(n-1);

    UFDS us(n);
    for (int i = n-2; i>=0; i--){
        for (int j : adjlist[i]){
            if (j<i){continue;}
            us.connect(i,j);
        }
    }
    us.geneulertour(0);

    //display(us.eulertour);
    //display(ue.eulertour);

    vector<int> sl(q), sr(q), el(q), er(q);

    getranges(us.eulertour, true, S, L, sl, sr); 
    getranges(ue.eulertour, false, E, R, el, er); 

    //display(sl);display(sr);
    //display(el);display(er);

    // s - x axis, e - y axis

    vector<pair<int,int>> coords;

    vector<vector<int>> yval2coord(n);
    for (int i = 0; i<ue.eulertour.size(); i++){
        yval2coord[ue.eulertour[i]].push_back(i);
    }

    for (int i = 0; i<us.eulertour.size(); i++){
        for (int y : yval2coord[us.eulertour[i]]){
            //cout<<i<<' '<<y<<'\n';
            coords.push_back({i,y});
        }
    }

    vector<pair<int,int>> rangequeries;
    vector<int> qans(2*q);
    for (int i = 0; i<q; i++){
        rangequeries.push_back({sl[i]-1,2*i});
        rangequeries.push_back({sr[i],2*i+1});
    }

    FenwickTree ft(ue.eulertour.size());

    sort(rangequeries.begin(),rangequeries.end());

    int ind = 0;

    for (int i = 0; i<2*q; i++){
        //cout<<"query: "<<rangequeries[i].first<<' '<<rangequeries[i].second<<'\n';
        //cout<<"for: "<<rangequeries[i].second/2<<'\n';
        if (rangequeries[i].first==-1){
            qans[rangequeries[i].second]=0;
            continue;
        }
        while (ind<coords.size()&&coords[ind].first<=rangequeries[i].first){
            ft.update(coords[ind].second);
            ind++;
        }
        int yrange = rangequeries[i].second/2;
        qans[rangequeries[i].second]=ft.query(el[yrange],er[yrange]);
        //cout<<qans[rangequeries[i].second]<<'\n';
    }

    vector<int> ans(q,0);

    for (int i = 0; i<q; i++){
        //cout<<"query "<<i<<endl;
        //cout<<qans[2*i+1]<<' '<<qans[2*i]<<'\n';
        if (qans[2*i+1]-qans[2*i]>0){
            ans[i]=1;
        }
    }

    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void getranges(std::vector<int>&, bool, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
werewolf.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i<seq.size(); i++){
      |                     ~^~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:176:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |     for (int i = 0; i<ue.eulertour.size(); i++){
      |                     ~^~~~~~~~~~~~~~~~~~~~
werewolf.cpp:180:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |     for (int i = 0; i<us.eulertour.size(); i++){
      |                     ~^~~~~~~~~~~~~~~~~~~~
werewolf.cpp:207:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |         while (ind<coords.size()&&coords[ind].first<=rangequeries[i].first){
      |                ~~~^~~~~~~~~~~~~~

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