oj.uz

Submission #372342

# Submission time Handle Problem Language Result Execution time Memory
372342 2021-02-27T18:08:29 Z denkendoemeer Werewolf (IOI18_werewolf) C++14
100 / 100
 899 ms 151660 KB 
#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int t[400005],sz[400005],l[400005],st[400005],en[400005],cur[400005],sz2[400005];
vector<int>g[400005],g2[400005],ev[400005];
set<int>nod[400005];
int n,m,q;
int findt(int x)
{
    if (x==t[x])
        return x;
    return t[x]=findt(t[x]);
}
void onion(int a,int b,bool tip)
{
    a=findt(a);
    b=findt(b);
    if (a==b)
        return ;
    if (sz[a]<sz[b])
        swap(a,b);
    if (tip==0)
        g[a].push_back(b);
    else
        for(auto it:nod[b])
            nod[a].insert(it);
    t[b]=a;
    sz[a]+=sz[b];
}
void dfs(int x)
{
    static int u=0;
    l[x]=++u;
    for(auto it:g[x])
        dfs(it);
}
vector<int>check_validity(int n2,vector<int>x,vector<int>y,vector<int>s,vector<int>e,vector<int>l2,vector<int>r)
{
    n=n2;
    m=x.size();
    q=s.size();
    vector<int>ans(q,0);
    iota(t,t+n,0);
    fill(sz,sz+n,1);
    int i;
    for(i=0;i<m;i++){
        g2[x[i]].push_back(y[i]);
        g2[y[i]].push_back(x[i]);
    }
    for(i=0;i<q;i++)
        ev[l2[i]].push_back(i);
    for(i=n-1;i>=0;i--){
        for(auto it:g2[i])
            if (i<it)
                onion(it,i,0);
        for(auto it:ev[i]){
            int nodi=findt(s[it]);
            cur[it]=nodi;
            sz2[it]=sz[nodi];
        }
        ev[i].clear();
    }
    for(i=0;i<n;i++){
        if (i==t[i]){
            dfs(i);
            break;
        }
    }
    for(i=0;i<q;i++){
        st[i]=l[cur[i]];
        en[i]=l[cur[i]]+sz2[i]-1;
        ev[r[i]].push_back(i);
    }
    for(i=0;i<n;i++)
        nod[i].insert(l[i]);
    iota(t,t+n,0);
    fill(sz,sz+n,1);
    for(i=0;i<n;i++){
        for(auto it:g2[i])
            if (it<i)
                onion(i,it,1);
        for(auto it:ev[i]){
            int nodi=findt(e[it]);
            auto it2=nod[nodi].lower_bound(st[it]);
            if (it2!=nod[nodi].end() && *(it2)<=en[it])
                ans[it]=1;
        }
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47360 KB Output is correct
2 Correct 32 ms 47340 KB Output is correct
3 Correct 33 ms 47340 KB Output is correct
4 Correct 38 ms 47340 KB Output is correct
5 Correct 32 ms 47468 KB Output is correct
6 Correct 32 ms 47340 KB Output is correct
7 Correct 32 ms 47340 KB Output is correct
8 Correct 32 ms 47340 KB Output is correct
9 Correct 32 ms 47340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47360 KB Output is correct
2 Correct 32 ms 47340 KB Output is correct
3 Correct 33 ms 47340 KB Output is correct
4 Correct 38 ms 47340 KB Output is correct
5 Correct 32 ms 47468 KB Output is correct
6 Correct 32 ms 47340 KB Output is correct
7 Correct 32 ms 47340 KB Output is correct
8 Correct 32 ms 47340 KB Output is correct
9 Correct 32 ms 47340 KB Output is correct
10 Correct 40 ms 48492 KB Output is correct
11 Correct 38 ms 48384 KB Output is correct
12 Correct 39 ms 48620 KB Output is correct
13 Correct 38 ms 48236 KB Output is correct
14 Correct 39 ms 48236 KB Output is correct
15 Correct 38 ms 48492 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 151500 KB Output is correct
2 Correct 538 ms 108780 KB Output is correct
3 Correct 589 ms 114544 KB Output is correct
4 Correct 695 ms 122732 KB Output is correct
5 Correct 712 ms 124240 KB Output is correct
6 Correct 830 ms 130532 KB Output is correct
7 Correct 862 ms 151660 KB Output is correct
8 Correct 537 ms 108876 KB Output is correct
9 Correct 576 ms 113768 KB Output is correct
10 Correct 582 ms 122228 KB Output is correct
11 Correct 630 ms 123820 KB Output is correct
12 Correct 731 ms 131308 KB Output is correct
13 Correct 520 ms 107532 KB Output is correct
14 Correct 528 ms 107616 KB Output is correct
15 Correct 548 ms 107592 KB Output is correct
16 Correct 523 ms 107584 KB Output is correct
17 Correct 837 ms 150764 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47360 KB Output is correct
2 Correct 32 ms 47340 KB Output is correct
3 Correct 33 ms 47340 KB Output is correct
4 Correct 38 ms 47340 KB Output is correct
5 Correct 32 ms 47468 KB Output is correct
6 Correct 32 ms 47340 KB Output is correct
7 Correct 32 ms 47340 KB Output is correct
8 Correct 32 ms 47340 KB Output is correct
9 Correct 32 ms 47340 KB Output is correct
10 Correct 40 ms 48492 KB Output is correct
11 Correct 38 ms 48384 KB Output is correct
12 Correct 39 ms 48620 KB Output is correct
13 Correct 38 ms 48236 KB Output is correct
14 Correct 39 ms 48236 KB Output is correct
15 Correct 38 ms 48492 KB Output is correct
16 Correct 899 ms 151500 KB Output is correct
17 Correct 538 ms 108780 KB Output is correct
18 Correct 589 ms 114544 KB Output is correct
19 Correct 695 ms 122732 KB Output is correct
20 Correct 712 ms 124240 KB Output is correct
21 Correct 830 ms 130532 KB Output is correct
22 Correct 862 ms 151660 KB Output is correct
23 Correct 537 ms 108876 KB Output is correct
24 Correct 576 ms 113768 KB Output is correct
25 Correct 582 ms 122228 KB Output is correct
26 Correct 630 ms 123820 KB Output is correct
27 Correct 731 ms 131308 KB Output is correct
28 Correct 520 ms 107532 KB Output is correct
29 Correct 528 ms 107616 KB Output is correct
30 Correct 548 ms 107592 KB Output is correct
31 Correct 523 ms 107584 KB Output is correct
32 Correct 837 ms 150764 KB Output is correct
33 Correct 782 ms 120556 KB Output is correct
34 Correct 332 ms 83176 KB Output is correct
35 Correct 772 ms 112612 KB Output is correct
36 Correct 823 ms 124160 KB Output is correct
37 Correct 785 ms 113252 KB Output is correct
38 Correct 789 ms 120428 KB Output is correct
39 Correct 761 ms 104428 KB Output is correct
40 Correct 805 ms 119264 KB Output is correct
41 Correct 696 ms 114152 KB Output is correct
42 Correct 755 ms 122804 KB Output is correct
43 Correct 788 ms 113252 KB Output is correct
44 Correct 767 ms 113452 KB Output is correct
45 Correct 649 ms 104348 KB Output is correct
46 Correct 718 ms 104172 KB Output is correct
47 Correct 562 ms 107496 KB Output is correct
48 Correct 538 ms 107512 KB Output is correct
49 Correct 535 ms 107488 KB Output is correct
50 Correct 527 ms 107532 KB Output is correct
51 Correct 794 ms 117476 KB Output is correct
52 Correct 798 ms 117348 KB Output is correct