oj.uz

Submission #730892

# Submission time Handle Problem Language Result Execution time Memory
730892 2023-04-26T15:02:44 Z PoonYaPat Werewolf (IOI18_werewolf) C++14
100 / 100
 853 ms 138040 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int p[200001],r[200001],cnt,in[200001],out[200001],pa[2][200001],va[2][200001],c[200001],top[2];
vector<int> adj[200001];
vector<pii> Adj[2][200001];

int find(int x) {
    while (x!=p[x]) x=p[x];
    return x;
}

void unite(int x, int y, int val, int mode) {
    x=find(x); y=find(y);
    if (x==y) return;

    if (r[x]>r[y]) {
        p[y]=x;
        Adj[mode][x].push_back(pii(y,val));
    } else if (r[x]<r[y]) {
        p[x]=y;
        Adj[mode][y].push_back(pii(x,val));
    } else {
        p[x]=y; ++r[y];
        Adj[mode][y].push_back(pii(x,val));
    }
}

int f0(int x, int bound) {
    if (bound>=va[0][x]) {
        while (x!=pa[0][x] && va[0][pa[0][x]]<=bound) x=pa[0][x];
        x=pa[0][x];
    }

    int l=0,r=Adj[0][x].size()-1;
    if (r==-1) return -1;
    if (Adj[0][x][0].second>bound) return -1;

    while (l<r) { //find the last element that not over bound
        int mid=(l+r+1)/2;
        if (Adj[0][x][mid].second<=bound) l=mid;
        else r=mid-1;
    }

    return Adj[0][x][l].first;
}

int f1(int x, int bound) {
    if (bound<=va[1][x]) {
        while (x!=pa[1][x] && va[1][pa[1][x]]>=bound) x=pa[1][x];
        x=pa[1][x];
    }

    int l=0,r=Adj[1][x].size()-1;
    if (r==-1) return -1;
    if (Adj[1][x][0].second<bound) return -1;

    while (l<r) { //find the last element that at least bound
        int mid=(l+r+1)/2;
        if (Adj[1][x][mid].second>=bound) l=mid;
        else r=mid-1;
    }

    return Adj[1][x][l].first;
}

void dfs(int x, int par, int mode) { //dfs in werewolf
    pa[mode][x]=par;
    if (!mode) c[x]=++cnt,in[x]=c[par];

    for (auto s : Adj[mode][x]) {
        va[mode][s.first]=s.second;
        dfs(s.first,x,mode);
    }

    if (!mode) out[x]=cnt;
}

struct N {
    int in,out,idx;
};
vector<N> v[200001];
set<int> temp[200001];
vector<int> ans;

void dfs_ans(int x) { //find answer in human
    temp[x].insert(c[x]);

    for (auto k : Adj[1][x]) {
        int s=k.first;
        dfs_ans(s);

        if (temp[x].size()<temp[s].size()) swap(temp[s],temp[x]);
        for (auto h : temp[s]) temp[x].insert(h);

        for (auto h : v[s]) {
            if (*(temp[x].lower_bound(h.in))<=h.out && temp[x].lower_bound(h.in)!=temp[x].end()) ans[h.idx]=1;
            else ans[h.idx]=0;
        }
    }
}

vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    for (int i=0; i<X.size(); ++i) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    for (int i=0; i<S.size(); ++i) ans.push_back(0);

    for (int i=0; i<n; ++i) p[i]=i,r[i]=1;
    for (int i=0; i<n; ++i) { //werewolf
        for (auto s : adj[i]) {
            if (s<i) unite(i,s,i,0);
        }
    }
    top[0]=find(0);
    va[0][top[0]]=n-1;
    dfs(top[0],top[0],0);

    for (int i=0; i<n; ++i) p[i]=i,r[i]=1;
    for (int i=n-1; i>=0; --i) { //human
        for (auto s : adj[i]) {
            if (s>i) unite(i,s,i,1);
        }
    }
    top[1]=find(0);
    dfs(top[1],top[1],1);

    for (int i=0; i<S.size(); ++i) {
        if (S[i]<L[i] || E[i]>R[i]) ans[i]=0;
        else {
            int s=f1(S[i],L[i]), e=f0(E[i],R[i]);

            if (s==-1 && e==-1) ans[i]=0;
            else if (s==-1) {
                if (c[S[i]]>=in[e] && c[S[i]]<=out[e]) ans[i]=1;
                else ans[i]=0;
            } else if (e==-1) v[s].push_back({c[E[i]],c[E[i]],i});
            else v[s].push_back({in[e],out[e],i});
        }
    }

    Adj[1][n].push_back({top[1],0});
    dfs_ans(n);
  
    return ans;
}

Compilation message

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:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i=0; i<X.size(); ++i) {
      |                   ~^~~~~~~~~
werewolf.cpp:110:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i=0; i<S.size(); ++i) ans.push_back(0);
      |                   ~^~~~~~~~~
werewolf.cpp:131:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for (int i=0; i<S.size(); ++i) {
      |                   ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 15 ms 28476 KB Output is correct
3 Correct 16 ms 28492 KB Output is correct
4 Correct 15 ms 28544 KB Output is correct
5 Correct 15 ms 28500 KB Output is correct
6 Correct 15 ms 28448 KB Output is correct
7 Correct 15 ms 28572 KB Output is correct
8 Correct 15 ms 28508 KB Output is correct
9 Correct 14 ms 28528 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 15 ms 28476 KB Output is correct
3 Correct 16 ms 28492 KB Output is correct
4 Correct 15 ms 28544 KB Output is correct
5 Correct 15 ms 28500 KB Output is correct
6 Correct 15 ms 28448 KB Output is correct
7 Correct 15 ms 28572 KB Output is correct
8 Correct 15 ms 28508 KB Output is correct
9 Correct 14 ms 28528 KB Output is correct
10 Correct 20 ms 29516 KB Output is correct
11 Correct 19 ms 29516 KB Output is correct
12 Correct 21 ms 29820 KB Output is correct
13 Correct 22 ms 29528 KB Output is correct
14 Correct 21 ms 29780 KB Output is correct
15 Correct 20 ms 29652 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 127584 KB Output is correct
2 Correct 486 ms 92456 KB Output is correct
3 Correct 530 ms 111828 KB Output is correct
4 Correct 678 ms 126852 KB Output is correct
5 Correct 707 ms 130056 KB Output is correct
6 Correct 704 ms 135208 KB Output is correct
7 Correct 853 ms 138040 KB Output is correct
8 Correct 543 ms 100616 KB Output is correct
9 Correct 514 ms 111116 KB Output is correct
10 Correct 613 ms 126552 KB Output is correct
11 Correct 552 ms 128008 KB Output is correct
12 Correct 692 ms 134256 KB Output is correct
13 Correct 560 ms 92148 KB Output is correct
14 Correct 551 ms 91872 KB Output is correct
15 Correct 531 ms 92096 KB Output is correct
16 Correct 602 ms 92092 KB Output is correct
17 Correct 837 ms 136180 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 15 ms 28476 KB Output is correct
3 Correct 16 ms 28492 KB Output is correct
4 Correct 15 ms 28544 KB Output is correct
5 Correct 15 ms 28500 KB Output is correct
6 Correct 15 ms 28448 KB Output is correct
7 Correct 15 ms 28572 KB Output is correct
8 Correct 15 ms 28508 KB Output is correct
9 Correct 14 ms 28528 KB Output is correct
10 Correct 20 ms 29516 KB Output is correct
11 Correct 19 ms 29516 KB Output is correct
12 Correct 21 ms 29820 KB Output is correct
13 Correct 22 ms 29528 KB Output is correct
14 Correct 21 ms 29780 KB Output is correct
15 Correct 20 ms 29652 KB Output is correct
16 Correct 718 ms 127584 KB Output is correct
17 Correct 486 ms 92456 KB Output is correct
18 Correct 530 ms 111828 KB Output is correct
19 Correct 678 ms 126852 KB Output is correct
20 Correct 707 ms 130056 KB Output is correct
21 Correct 704 ms 135208 KB Output is correct
22 Correct 853 ms 138040 KB Output is correct
23 Correct 543 ms 100616 KB Output is correct
24 Correct 514 ms 111116 KB Output is correct
25 Correct 613 ms 126552 KB Output is correct
26 Correct 552 ms 128008 KB Output is correct
27 Correct 692 ms 134256 KB Output is correct
28 Correct 560 ms 92148 KB Output is correct
29 Correct 551 ms 91872 KB Output is correct
30 Correct 531 ms 92096 KB Output is correct
31 Correct 602 ms 92092 KB Output is correct
32 Correct 837 ms 136180 KB Output is correct
33 Correct 737 ms 106460 KB Output is correct
34 Correct 312 ms 63716 KB Output is correct
35 Correct 661 ms 97224 KB Output is correct
36 Correct 678 ms 108480 KB Output is correct
37 Correct 669 ms 98144 KB Output is correct
38 Correct 704 ms 105892 KB Output is correct
39 Correct 647 ms 112052 KB Output is correct
40 Correct 629 ms 105448 KB Output is correct
41 Correct 616 ms 98976 KB Output is correct
42 Correct 648 ms 107896 KB Output is correct
43 Correct 704 ms 98348 KB Output is correct
44 Correct 604 ms 97808 KB Output is correct
45 Correct 663 ms 102524 KB Output is correct
46 Correct 632 ms 113288 KB Output is correct
47 Correct 550 ms 92396 KB Output is correct
48 Correct 518 ms 92444 KB Output is correct
49 Correct 531 ms 92288 KB Output is correct
50 Correct 510 ms 92088 KB Output is correct
51 Correct 672 ms 105248 KB Output is correct
52 Correct 647 ms 104892 KB Output is correct