oj.uz

Submission #987389

# Submission time Handle Problem Language Result Execution time Memory
987389 2024-05-22T16:54:30 Z yeediot Werewolf (IOI18_werewolf) C++17
100 / 100
 1680 ms 100488 KB 
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#else
#include "werewolf.h"
void setio(){}
#endif
#define why_TOI_is_so_de ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);setio();
const int mxn=2e5+5;
int n;
vector<int>adj2[mxn];
struct DSU{
    vector<int>to;
    void init(){
        to.resize(n+1);
        for(int i=0;i<=n;i++){
            to[i]=i;
        }
    }
    int find(int x){
        return x==to[x]?x:to[x]=find(to[x]);
    }
}d;
struct tree{
    vector<vector<int>>adj,jump;
    vector<tuple<int,int,int>>edges;
    int flg, timer, in[mxn], out[mxn], ord[mxn];
    void init(int f){
        adj.resize(n+1);
        flg=f;
        jump.resize(20,vector<int>(n+1));
    }
    void dfs(int v,int pa){
        in[v]=++timer;
        ord[timer]=v;
        jump[0][v]=pa;
        for(auto u:adj[v]){
            if(u!=pa)dfs(u,v);
        }
        out[v]=timer;
    }
    void build(){
        for(int i=1;i<20;i++){
            for(int j=1;j<=n;j++){
                jump[i][j]=jump[i-1][jump[i-1][j]];
            }
        }
    }
    int find(int st,int x){
        if(flg){
            for(int i=19;i>=0;i--){
                if(jump[i][st]<=x){
                    st=jump[i][st];
                }
            }
        }
        else{
            for(int i=19;i>=0;i--){
                if(jump[i][st]>=x){
                    st=jump[i][st];
                }
            }
        }
        return st;
    }
}mn, mx;
vector<int>upd(mxn),ans;
vector<tuple<int,int,int,int>>in[mxn];
int bit[mxn];
void modify(int p){
    for(;p<=n;p+=p&-p){
        bit[p]++;
    }
}
int query(int p){
    int res=0;
    for(;p;p-=p&-p){
        res+=bit[p];
    }
    return res;
}
vi check_validity(int N,vi X,vi Y,vi S,vi E,vi L,vi R){
    why_TOI_is_so_de;
    n=N;
    ans.resize(sz(E));
    for(int i=0;i<sz(X);i++){
        int a=X[i],b=Y[i];
        a++;
        b++;
        adj2[a].pb(b);
        adj2[b].pb(a);
    }
    mn.init(1);
    mx.init(0);
    d.init();
    for(int x=n;x>=1;x--){
        for(auto y:adj2[x]){
            if(y<x)continue;
            int fx=d.find(y),fy=d.find(x);
            if(fx==fy)continue;
            mx.adj[fy].pb(fx);
            d.to[fx]=fy;
        }
    }
    d.init();
    for(int x=1;x<=n;x++){
        for(auto y:adj2[x]){
            if(y>x)continue;
            int fx=d.find(y),fy=d.find(x);
            if(fx==fy)continue;
            mn.adj[fy].pb(fx);
            d.to[fx]=fy;
        }
    }
    mn.dfs(n,n);
    mx.dfs(1,1);
    mn.build();
    mx.build();
    for(int i=1;i<=n;i++){
        upd[i]=mn.in[mx.ord[i]];
    }
    for(int i=0;i<sz(S);i++){
        int s=S[i]+1,e=E[i]+1,l=L[i]+1,r=R[i]+1;
        int fs=mx.find(s,l),se=mn.find(e,r);
        in[mx.in[fs]-1].pb({mn.in[se],mn.out[se],i,-1});
        in[mx.out[fs]].pb({mn.in[se],mn.out[se],i,1});
    }
    for(int i=1;i<=n;i++){
        modify(upd[i]);
        for(auto [l,r,id,flg]:in[i]){
            ans[id]+=flg*(query(r)-query(l-1));
        }
    }
    for(int i=0;i<sz(E);i++){
        if(ans[i])ans[i]=1;
    }
    return ans;
}
/*
input:
 [fx,fy] = [2, 3]
[fx,fy] = [3, 4]
[fx,fy] = [1, 4]
[fx,fy] = [4, 5]
[fx,fy] = [5, 6]
[fx,fy] = [5, 4]
[fx,fy] = [6, 3]
[fx,fy] = [3, 2]
[fx,fy] = [4, 2]
[fx,fy] = [2, 1]
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10584 KB Output is correct
2 Correct 6 ms 10844 KB Output is correct
3 Correct 7 ms 10584 KB Output is correct
4 Correct 6 ms 10588 KB Output is correct
5 Correct 6 ms 10588 KB Output is correct
6 Correct 6 ms 10588 KB Output is correct
7 Correct 7 ms 10588 KB Output is correct
8 Correct 5 ms 10588 KB Output is correct
9 Correct 7 ms 10588 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10584 KB Output is correct
2 Correct 6 ms 10844 KB Output is correct
3 Correct 7 ms 10584 KB Output is correct
4 Correct 6 ms 10588 KB Output is correct
5 Correct 6 ms 10588 KB Output is correct
6 Correct 6 ms 10588 KB Output is correct
7 Correct 7 ms 10588 KB Output is correct
8 Correct 5 ms 10588 KB Output is correct
9 Correct 7 ms 10588 KB Output is correct
10 Correct 10 ms 11868 KB Output is correct
11 Correct 10 ms 11792 KB Output is correct
12 Correct 10 ms 11868 KB Output is correct
13 Correct 11 ms 12016 KB Output is correct
14 Correct 11 ms 11864 KB Output is correct
15 Correct 11 ms 11868 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1500 ms 92944 KB Output is correct
2 Correct 746 ms 94784 KB Output is correct
3 Correct 852 ms 92816 KB Output is correct
4 Correct 683 ms 91352 KB Output is correct
5 Correct 926 ms 92024 KB Output is correct
6 Correct 1203 ms 92756 KB Output is correct
7 Correct 1083 ms 91588 KB Output is correct
8 Correct 579 ms 94664 KB Output is correct
9 Correct 370 ms 91452 KB Output is correct
10 Correct 263 ms 91204 KB Output is correct
11 Correct 347 ms 91204 KB Output is correct
12 Correct 310 ms 91456 KB Output is correct
13 Correct 1128 ms 98560 KB Output is correct
14 Correct 1053 ms 98728 KB Output is correct
15 Correct 1052 ms 98560 KB Output is correct
16 Correct 1102 ms 98824 KB Output is correct
17 Correct 1197 ms 91116 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10584 KB Output is correct
2 Correct 6 ms 10844 KB Output is correct
3 Correct 7 ms 10584 KB Output is correct
4 Correct 6 ms 10588 KB Output is correct
5 Correct 6 ms 10588 KB Output is correct
6 Correct 6 ms 10588 KB Output is correct
7 Correct 7 ms 10588 KB Output is correct
8 Correct 5 ms 10588 KB Output is correct
9 Correct 7 ms 10588 KB Output is correct
10 Correct 10 ms 11868 KB Output is correct
11 Correct 10 ms 11792 KB Output is correct
12 Correct 10 ms 11868 KB Output is correct
13 Correct 11 ms 12016 KB Output is correct
14 Correct 11 ms 11864 KB Output is correct
15 Correct 11 ms 11868 KB Output is correct
16 Correct 1500 ms 92944 KB Output is correct
17 Correct 746 ms 94784 KB Output is correct
18 Correct 852 ms 92816 KB Output is correct
19 Correct 683 ms 91352 KB Output is correct
20 Correct 926 ms 92024 KB Output is correct
21 Correct 1203 ms 92756 KB Output is correct
22 Correct 1083 ms 91588 KB Output is correct
23 Correct 579 ms 94664 KB Output is correct
24 Correct 370 ms 91452 KB Output is correct
25 Correct 263 ms 91204 KB Output is correct
26 Correct 347 ms 91204 KB Output is correct
27 Correct 310 ms 91456 KB Output is correct
28 Correct 1128 ms 98560 KB Output is correct
29 Correct 1053 ms 98728 KB Output is correct
30 Correct 1052 ms 98560 KB Output is correct
31 Correct 1102 ms 98824 KB Output is correct
32 Correct 1197 ms 91116 KB Output is correct
33 Correct 1680 ms 93148 KB Output is correct
34 Correct 211 ms 38776 KB Output is correct
35 Correct 1562 ms 94996 KB Output is correct
36 Correct 1538 ms 93244 KB Output is correct
37 Correct 1516 ms 94248 KB Output is correct
38 Correct 1134 ms 93892 KB Output is correct
39 Correct 1144 ms 100488 KB Output is correct
40 Correct 722 ms 97984 KB Output is correct
41 Correct 445 ms 92752 KB Output is correct
42 Correct 358 ms 91132 KB Output is correct
43 Correct 580 ms 98112 KB Output is correct
44 Correct 581 ms 94344 KB Output is correct
45 Correct 385 ms 100068 KB Output is correct
46 Correct 459 ms 99556 KB Output is correct
47 Correct 1102 ms 98788 KB Output is correct
48 Correct 995 ms 98664 KB Output is correct
49 Correct 778 ms 98820 KB Output is correct
50 Correct 761 ms 98516 KB Output is correct
51 Correct 426 ms 98252 KB Output is correct
52 Correct 478 ms 98112 KB Output is correct