oj.uz

Submission #173423

# Submission time Handle Problem Language Result Execution time Memory
173423 2020-01-04T05:17:56 Z errorgorn Werewolf (IOI18_werewolf) C++14
100 / 100
 1129 ms 153936 KB 
#include "werewolf.h"
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;

struct query{
    int s,e;
    int l,r;
    int index;

    query(int a,int b,int c,int d,int _index){
        s=a,e=b,l=c,r=d;
        index=_index;
    }
};

int n,m,q;
vector<int> al[200005];
vector<iii> edges;
vector<query*> __q;

///for kruskal tree
ii range[400005];
int lchild[400005];
int rchild[400005];
int edgew[400005];
int parent[400005][20];

int __IDX;
int __LEAFY;

struct UFDS{
    int p[400005];
    int r[400005];

    UFDS(){
        for (int x=0;x<400005;x++){
            p[x]=x;
            r[x]=0;
        }
    }

    int parent(int i){return (p[i]==i)?i:p[i]=parent(p[i]);}

    void unions(int i,int j,int k){
        i=parent(i),j=parent(j);
        if (i==j) return;
        p[i]=__IDX;
        p[j]=__IDX;
        lchild[__IDX]=i;
        rchild[__IDX]=j;
        edgew[__IDX]=k;
        __IDX++;
    }
}*dsu=new UFDS();

void dfs(int i){
    if (i<n){
        range[i]=ii(__LEAFY,__LEAFY);
        __LEAFY++;
        return;
    }
    int curr;
    curr=parent[lchild[i]][0]=i;
    for (int x=0;parent[curr][x]!=-1;x++){
        curr=parent[lchild[i]][x+1]=parent[curr][x];
    }
    dfs(lchild[i]);
    curr=parent[rchild[i]][0]=i;
    for (int x=0;parent[curr][x]!=-1;x++){
        curr=parent[rchild[i]][x+1]=parent[curr][x];
    }
    dfs(rchild[i]);
    range[i]=ii(range[lchild[i]].first,range[rchild[i]].second);
}

set<int> components[200005];
int pos[200005];
int fin[200005];
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();

    for (int x=0;x<m;x++){
        edges.push_back(iii(min(X[x],Y[x]),ii(X[x],Y[x])));
    }

    sort(edges.begin(),edges.end());
    reverse(edges.begin(),edges.end());

    __IDX=n;
    __LEAFY=0;
    for (auto &it:edges){
        dsu->unions(it.second.first,it.second.second,it.first);
    }

    memset(parent,-1,sizeof(parent));
    dfs(__IDX-1);

    edges.clear();
    for (int x=0;x<m;x++){
        edges.push_back(iii(max(X[x],Y[x]),ii(range[X[x]].first,range[Y[x]].first)));
    }
    sort(edges.begin(),edges.end());
    reverse(edges.begin(),edges.end());

    for (int x=0;x<n;x++){
        components[x].insert(x);
        pos[x]=x;
    }

    for (int x=0;x<q;x++){
        __q.push_back(new query(S[x],E[x],L[x],R[x],x));
    }
    sort (__q.begin(),__q.end(),[](query *i,query *j){
       return i->r<j->r;
    });

    int s,e,l,r;
    int i,j;
    set<int>::iterator __it;
    for (int x=0;x<q;x++){
        s=__q[x]->s,e=__q[x]->e,l=__q[x]->l,r=__q[x]->r;

        while (!edges.empty() && edges.back().first<=r){
            i=edges.back().second.first,j=edges.back().second.second;
            edges.pop_back();
            if (pos[i]==pos[j]) continue;
            if (components[pos[i]].size()>components[pos[j]].size()) swap(i,j);
            for (auto &it:components[pos[i]]){
                pos[it]=pos[j];
                components[pos[j]].insert(it);
            }
        }

        for (int x=19;~x;x--){
            if (parent[s][x]!=-1 && edgew[parent[s][x]]>=l) s=parent[s][x];
        }

        i=range[s].first,j=range[s].second;
        e=range[e].first;
        __it=components[pos[e]].lower_bound(i);
        if (__it!=components[pos[e]].end() && (*__it)<=j) fin[__q[x]->index]=1;
        else fin[__q[x]->index]=0;
    }

    vector<int> ans;
    for (int x=0;x<q;x++){
        ans.push_back(fin[x]);
    }

    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 49020 KB Output is correct
2 Correct 45 ms 48888 KB Output is correct
3 Correct 44 ms 48888 KB Output is correct
4 Correct 44 ms 48888 KB Output is correct
5 Correct 44 ms 48888 KB Output is correct
6 Correct 44 ms 49004 KB Output is correct
7 Correct 46 ms 48888 KB Output is correct
8 Correct 45 ms 48888 KB Output is correct
9 Correct 45 ms 48892 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 49020 KB Output is correct
2 Correct 45 ms 48888 KB Output is correct
3 Correct 44 ms 48888 KB Output is correct
4 Correct 44 ms 48888 KB Output is correct
5 Correct 44 ms 48888 KB Output is correct
6 Correct 44 ms 49004 KB Output is correct
7 Correct 46 ms 48888 KB Output is correct
8 Correct 45 ms 48888 KB Output is correct
9 Correct 45 ms 48892 KB Output is correct
10 Correct 52 ms 50040 KB Output is correct
11 Correct 51 ms 49912 KB Output is correct
12 Correct 52 ms 50148 KB Output is correct
13 Correct 51 ms 49788 KB Output is correct
14 Correct 51 ms 49876 KB Output is correct
15 Correct 53 ms 50040 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1042 ms 152148 KB Output is correct
2 Correct 787 ms 110564 KB Output is correct
3 Correct 729 ms 115112 KB Output is correct
4 Correct 740 ms 123368 KB Output is correct
5 Correct 770 ms 124844 KB Output is correct
6 Correct 869 ms 131304 KB Output is correct
7 Correct 904 ms 153936 KB Output is correct
8 Correct 738 ms 110516 KB Output is correct
9 Correct 559 ms 115172 KB Output is correct
10 Correct 595 ms 123340 KB Output is correct
11 Correct 636 ms 124632 KB Output is correct
12 Correct 708 ms 131996 KB Output is correct
13 Correct 874 ms 112520 KB Output is correct
14 Correct 938 ms 112488 KB Output is correct
15 Correct 878 ms 112396 KB Output is correct
16 Correct 896 ms 112436 KB Output is correct
17 Correct 942 ms 153060 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 49020 KB Output is correct
2 Correct 45 ms 48888 KB Output is correct
3 Correct 44 ms 48888 KB Output is correct
4 Correct 44 ms 48888 KB Output is correct
5 Correct 44 ms 48888 KB Output is correct
6 Correct 44 ms 49004 KB Output is correct
7 Correct 46 ms 48888 KB Output is correct
8 Correct 45 ms 48888 KB Output is correct
9 Correct 45 ms 48892 KB Output is correct
10 Correct 52 ms 50040 KB Output is correct
11 Correct 51 ms 49912 KB Output is correct
12 Correct 52 ms 50148 KB Output is correct
13 Correct 51 ms 49788 KB Output is correct
14 Correct 51 ms 49876 KB Output is correct
15 Correct 53 ms 50040 KB Output is correct
16 Correct 1042 ms 152148 KB Output is correct
17 Correct 787 ms 110564 KB Output is correct
18 Correct 729 ms 115112 KB Output is correct
19 Correct 740 ms 123368 KB Output is correct
20 Correct 770 ms 124844 KB Output is correct
21 Correct 869 ms 131304 KB Output is correct
22 Correct 904 ms 153936 KB Output is correct
23 Correct 738 ms 110516 KB Output is correct
24 Correct 559 ms 115172 KB Output is correct
25 Correct 595 ms 123340 KB Output is correct
26 Correct 636 ms 124632 KB Output is correct
27 Correct 708 ms 131996 KB Output is correct
28 Correct 874 ms 112520 KB Output is correct
29 Correct 938 ms 112488 KB Output is correct
30 Correct 878 ms 112396 KB Output is correct
31 Correct 896 ms 112436 KB Output is correct
32 Correct 942 ms 153060 KB Output is correct
33 Correct 958 ms 121564 KB Output is correct
34 Correct 500 ms 88412 KB Output is correct
35 Correct 1022 ms 116144 KB Output is correct
36 Correct 926 ms 125024 KB Output is correct
37 Correct 1004 ms 116200 KB Output is correct
38 Correct 924 ms 121912 KB Output is correct
39 Correct 876 ms 104828 KB Output is correct
40 Correct 1061 ms 124712 KB Output is correct
41 Correct 836 ms 116780 KB Output is correct
42 Correct 733 ms 124536 KB Output is correct
43 Correct 1129 ms 118872 KB Output is correct
44 Correct 937 ms 116596 KB Output is correct
45 Correct 686 ms 105700 KB Output is correct
46 Correct 709 ms 104728 KB Output is correct
47 Correct 855 ms 112740 KB Output is correct
48 Correct 833 ms 112380 KB Output is correct
49 Correct 859 ms 112724 KB Output is correct
50 Correct 846 ms 112484 KB Output is correct
51 Correct 1002 ms 124624 KB Output is correct
52 Correct 1000 ms 125020 KB Output is correct