oj.uz

Submission #133482

# Submission time Handle Problem Language Result Execution time Memory
133482 2019-07-20T21:59:05 Z thebes Werewolf (IOI18_werewolf) C++14
100 / 100
 1014 ms 103148 KB 
#include <bits/stdc++.h>
using namespace std;

const int MN = 4e5+5, LG = 20;
int ds[MN], p[MN], rep[MN], N, M, Q, i, j, vis[MN][2], nxt, sp[MN][LG], rev[MN], mp[MN], ans[MN];
struct edge{int x, y;}; vector<edge> ee;
vector<int> adj[MN];
int fnd(int x){return ds[x]=ds[x]==x?x:fnd(ds[x]);}
pair<int,int> a[MN]; set<int> st[MN];
struct qur{int s, r, id;}; vector<qur> q;

void dfs(int n){
    vis[n][0]=++nxt; rev[nxt]=n; mp[n]=nxt;
    sp[n][0]=p[n];
    for(auto v : adj[n])
        dfs(v);
    vis[n][1]=nxt;
}

int anc(int n,int h){
    for(int i=LG-1;i>=0;i--){
        if(sp[n][i]>=h) n=sp[n][i];
    }
    return 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){
    N = n; M = x.size(); Q = s.size();
    for(i=0;i<M;i++) ee.push_back({x[i]+1,y[i]+1});
    for(i=0;i<Q;i++) s[i]++,e[i]++,l[i]++,r[i]++;
    for(i=1;i<=N;i++) ds[i]=i,rep[i]=i;
    for(i=0;i<ee.size();i++){if(ee[i].x<ee[i].y)swap(ee[i].x,ee[i].y);}
    sort(ee.begin(),ee.end(),[](edge i,edge j){return i.y>j.y;});
    for(auto v : ee){
        if(fnd(v.x)!=fnd(v.y)){
            int x = fnd(v.x), y = fnd(v.y);
            if(rep[x]>rep[y]) swap(x,y);
            adj[rep[x]].push_back(rep[y]);
            ds[y] = x; p[y] = x;
        }
    }
    dfs(1);
    for(j=1;j<LG;j++){
        for(i=1;i<=N;i++)
            sp[i][j]=sp[sp[i][j-1]][j-1];
    }
    for(i=0;i<Q;i++){
        int x = anc(s[i], l[i]);
        a[i+1]={vis[x][0],vis[x][1]};
        q.push_back({e[i],r[i],i+1});
    }
    sort(q.begin(),q.end(),[](qur i,qur j){return i.r<j.r;});
    for(i=1;i<=N;i++) ds[i]=i,st[i].insert(i);
    for(i=0;i<ee.size();i++) swap(ee[i].x,ee[i].y);
    sort(ee.begin(),ee.end(),[](edge i,edge j){return i.y<j.y;});
    i = 0;
    for(auto v : ee){
        while(i<q.size()&&q[i].r<v.y){
            int x = fnd(mp[q[i].s]);
            int id = q[i].id;
            auto it = st[x].lower_bound(a[id].first);
            if(it!=st[x].end()&&*it<=a[id].second) ans[id]=1;
            i++;
        }
        if(fnd(mp[v.x])!=fnd(mp[v.y])){
            int x = fnd(mp[v.x]), y = fnd(mp[v.y]);
            if(st[x].size()>st[y].size()) swap(x,y);
            for(auto v : st[x]) st[y].insert(v);
            st[x].clear();
            ds[x] = y;
        }
    }
    while(i<q.size()){
        int x = fnd(q[i].s);
        int id = q[i].id;
        auto it = st[x].lower_bound(a[id].first);
        if(it!=st[x].end()&&*it<=a[id].second) ans[id]=1;
        i++;
    }
    vector<int> res;
    for(i=1;i<=Q;i++) res.push_back(ans[i]);
    return res;
}

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:32:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<ee.size();i++){if(ee[i].x<ee[i].y)swap(ee[i].x,ee[i].y);}
             ~^~~~~~~~~~
werewolf.cpp:54:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<ee.size();i++) swap(ee[i].x,ee[i].y);
             ~^~~~~~~~~~
werewolf.cpp:58:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i<q.size()&&q[i].r<v.y){
               ~^~~~~~~~~
werewolf.cpp:73:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i<q.size()){
           ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 28664 KB Output is correct
2 Correct 32 ms 28536 KB Output is correct
3 Correct 29 ms 28508 KB Output is correct
4 Correct 33 ms 28536 KB Output is correct
5 Correct 27 ms 28536 KB Output is correct
6 Correct 27 ms 28664 KB Output is correct
7 Correct 27 ms 28664 KB Output is correct
8 Correct 27 ms 28664 KB Output is correct
9 Correct 27 ms 28536 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 28664 KB Output is correct
2 Correct 32 ms 28536 KB Output is correct
3 Correct 29 ms 28508 KB Output is correct
4 Correct 33 ms 28536 KB Output is correct
5 Correct 27 ms 28536 KB Output is correct
6 Correct 27 ms 28664 KB Output is correct
7 Correct 27 ms 28664 KB Output is correct
8 Correct 27 ms 28664 KB Output is correct
9 Correct 27 ms 28536 KB Output is correct
10 Correct 34 ms 29564 KB Output is correct
11 Correct 34 ms 29560 KB Output is correct
12 Correct 34 ms 29560 KB Output is correct
13 Correct 34 ms 29520 KB Output is correct
14 Correct 34 ms 29560 KB Output is correct
15 Correct 41 ms 29688 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 864 ms 84568 KB Output is correct
2 Correct 610 ms 89960 KB Output is correct
3 Correct 592 ms 89200 KB Output is correct
4 Correct 663 ms 89316 KB Output is correct
5 Correct 670 ms 89316 KB Output is correct
6 Correct 752 ms 89700 KB Output is correct
7 Correct 896 ms 92360 KB Output is correct
8 Correct 570 ms 89956 KB Output is correct
9 Correct 501 ms 89316 KB Output is correct
10 Correct 530 ms 89316 KB Output is correct
11 Correct 561 ms 89444 KB Output is correct
12 Correct 650 ms 90240 KB Output is correct
13 Correct 659 ms 99144 KB Output is correct
14 Correct 633 ms 99260 KB Output is correct
15 Correct 652 ms 99172 KB Output is correct
16 Correct 657 ms 99172 KB Output is correct
17 Correct 879 ms 92776 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 28664 KB Output is correct
2 Correct 32 ms 28536 KB Output is correct
3 Correct 29 ms 28508 KB Output is correct
4 Correct 33 ms 28536 KB Output is correct
5 Correct 27 ms 28536 KB Output is correct
6 Correct 27 ms 28664 KB Output is correct
7 Correct 27 ms 28664 KB Output is correct
8 Correct 27 ms 28664 KB Output is correct
9 Correct 27 ms 28536 KB Output is correct
10 Correct 34 ms 29564 KB Output is correct
11 Correct 34 ms 29560 KB Output is correct
12 Correct 34 ms 29560 KB Output is correct
13 Correct 34 ms 29520 KB Output is correct
14 Correct 34 ms 29560 KB Output is correct
15 Correct 41 ms 29688 KB Output is correct
16 Correct 864 ms 84568 KB Output is correct
17 Correct 610 ms 89960 KB Output is correct
18 Correct 592 ms 89200 KB Output is correct
19 Correct 663 ms 89316 KB Output is correct
20 Correct 670 ms 89316 KB Output is correct
21 Correct 752 ms 89700 KB Output is correct
22 Correct 896 ms 92360 KB Output is correct
23 Correct 570 ms 89956 KB Output is correct
24 Correct 501 ms 89316 KB Output is correct
25 Correct 530 ms 89316 KB Output is correct
26 Correct 561 ms 89444 KB Output is correct
27 Correct 650 ms 90240 KB Output is correct
28 Correct 659 ms 99144 KB Output is correct
29 Correct 633 ms 99260 KB Output is correct
30 Correct 652 ms 99172 KB Output is correct
31 Correct 657 ms 99172 KB Output is correct
32 Correct 879 ms 92776 KB Output is correct
33 Correct 859 ms 90416 KB Output is correct
34 Correct 419 ms 63872 KB Output is correct
35 Correct 848 ms 91904 KB Output is correct
36 Correct 786 ms 90244 KB Output is correct
37 Correct 817 ms 90984 KB Output is correct
38 Correct 792 ms 90596 KB Output is correct
39 Correct 841 ms 88420 KB Output is correct
40 Correct 1014 ms 102788 KB Output is correct
41 Correct 731 ms 90496 KB Output is correct
42 Correct 703 ms 90400 KB Output is correct
43 Correct 963 ms 96480 KB Output is correct
44 Correct 771 ms 91112 KB Output is correct
45 Correct 712 ms 89004 KB Output is correct
46 Correct 689 ms 88428 KB Output is correct
47 Correct 646 ms 99300 KB Output is correct
48 Correct 724 ms 99304 KB Output is correct
49 Correct 655 ms 99276 KB Output is correct
50 Correct 736 ms 99148 KB Output is correct
51 Correct 891 ms 103108 KB Output is correct
52 Correct 870 ms 103148 KB Output is correct