oj.uz

Submission #1052243

# Submission time Handle Problem Language Result Execution time Memory
1052243 2024-08-10T12:41:00 Z Ahmed57 Werewolf (IOI18_werewolf) C++17
100 / 100
 580 ms 188476 KB 
#include "bits/stdc++.h"

using namespace std;
int pr[600001];
int sp[600001];
int val1[600001];
int val2[600001];
vector<int> MI[600001];
vector<int> MA[600001];
int find(int x){
    if(x==pr[x])return x;
    return pr[x] = find(pr[x]);
}
bool mergegroup(int a,int b){
    a = find(a) , b = find(b);
    if(a==b)return 0;
    pr[a] = b;
    return 1;
}
int P[600001][20][2];
int timer = 0;
int in[600001][2];
int out[600001][2];
void dfs1(int i,int pr){
    P[i][0][0] = pr;
    in[i][0] = ++timer;
    for(int j = 1;j<20;j++){
        P[i][j][0] = P[P[i][j-1][0]][j-1][0];
    }
    for(auto j:MI[i]){
        if(j==pr)continue;
        dfs1(j,i);
    }
    out[i][0] = timer;
}
int rev[600001];
int n,m,q;
void dfs2(int i,int pr){
    in[i][1] = ++timer;
    if(i<n)rev[timer] = i;
    else rev[timer] = -1;
    P[i][0][1] = pr;
    for(int j = 1;j<20;j++){
        P[i][j][1] = P[P[i][j-1][1]][j-1][1];
    }
    for(auto j:MA[i]){
        if(j==pr)continue;
        dfs2(j,i);
    }
    out[i][1] = timer;
}
int seg[2400001];
void build(int p,int l,int r){
    seg[p] = 1e9;
    if(l==r)return ;
    int md = (l+r)/2;
    build(p*2,l,md);
    build(p*2+1,md+1,r);
}
void update(int p,int l,int r,int idx,int val){
    if(l==r){
        seg[p] = val;
        return ;
    }
    int md = (l+r)/2;
    if(idx<=md)update(p*2,l,md,idx,val);
    else update(p*2+1,md+1,r,idx,val);
    seg[p] = min(seg[p*2],seg[p*2+1]);
}
int query(int p,int l,int r,int lq,int rq){
    if(l>=lq&&r<=rq)return seg[p];
    if(r<lq||l>rq)return 1e9;
    int md = (l+r)/2;
    return min(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R){
    m = X.size();
    q = L.size();
    n = N;
    vector<array<int,3>> mi,ma;
    for(int i = 0;i<m;i++){
        mi.push_back({max(X[i],Y[i]),X[i],Y[i]});
        ma.push_back({min(X[i],Y[i]),X[i],Y[i]});
    }
    sort(mi.begin(),mi.end());
    sort(ma.begin(),ma.end());
    reverse(ma.begin(),ma.end());
    for(int i = 0;i<n;i++){
        pr[i] = i;
        sp[i] = i;
        val1[i] = i;
    }
    int nc = n;
    for(auto i:mi){
        if(find(i[1])==find(i[2]))continue;
        int A = find(i[1]);
        int B = find(i[2]);
        MI[nc].push_back(sp[A]);
        MI[nc].push_back(sp[B]);
        val1[nc] = i[0];
        mergegroup(i[1],i[2]);
        sp[find(i[1])] = nc;
        nc++;
    }
    for(int i = 0;i<n;i++){
        pr[i] = i;
        sp[i] = i;
        val2[i] = i;
    }
    nc = n;
    for(auto i:ma){
        if(find(i[1])==find(i[2]))continue;
        int A = find(i[1]);
        int B = find(i[2]);
        MA[nc].push_back(sp[A]);
        MA[nc].push_back(sp[B]);
        val2[nc] = i[0];
        mergegroup(i[1],i[2]);
        sp[find(i[1])] = nc;
        nc++;
    }
    timer = 0;
    dfs1(nc-1,nc-1);
    int nah = timer;
    timer = 0;
    dfs2(nc-1,nc-1);
    vector<array<int,4>> rngs[600001];
    for(int i = 0;i<q;i++){
        for(int j = 19;j>=0;j--){
            if(val2[P[S[i]][j][1]]>=L[i]){
                S[i] = P[S[i]][j][1];
            }
        }
        for(int j = 19;j>=0;j--){
            if(val1[P[E[i]][j][0]]<=R[i]){
                E[i] = P[E[i]][j][0];
            }
        }
        rngs[in[S[i]][1]].push_back({out[S[i]][1],in[E[i]][0],out[E[i]][0],i});
    }
    build(1,1,timer);
    vector<int> ANS(q,0);
    for(int i = timer;i>=1;i--){
        if(rev[i]!=-1){
            int no = rev[i];
            update(1,1,timer,in[no][0],i);
        }
        for(auto j:rngs[i]){
            if(query(1,1,timer,j[1],j[2])<=j[0]){
                ANS[j[3]] = 1;
            }else ANS[j[3]] = 0;
        }
    }
    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:124:9: warning: unused variable 'nah' [-Wunused-variable]
  124 |     int nah = timer;
      |         ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 59484 KB Output is correct
2 Correct 15 ms 59584 KB Output is correct
3 Correct 12 ms 59484 KB Output is correct
4 Correct 13 ms 59484 KB Output is correct
5 Correct 14 ms 59692 KB Output is correct
6 Correct 12 ms 59652 KB Output is correct
7 Correct 13 ms 59480 KB Output is correct
8 Correct 12 ms 59460 KB Output is correct
9 Correct 12 ms 59484 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 59484 KB Output is correct
2 Correct 15 ms 59584 KB Output is correct
3 Correct 12 ms 59484 KB Output is correct
4 Correct 13 ms 59484 KB Output is correct
5 Correct 14 ms 59692 KB Output is correct
6 Correct 12 ms 59652 KB Output is correct
7 Correct 13 ms 59480 KB Output is correct
8 Correct 12 ms 59460 KB Output is correct
9 Correct 12 ms 59484 KB Output is correct
10 Correct 18 ms 60252 KB Output is correct
11 Correct 15 ms 60292 KB Output is correct
12 Correct 16 ms 60252 KB Output is correct
13 Correct 18 ms 60400 KB Output is correct
14 Correct 16 ms 60200 KB Output is correct
15 Correct 22 ms 60248 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 166696 KB Output is correct
2 Correct 443 ms 178992 KB Output is correct
3 Correct 423 ms 176184 KB Output is correct
4 Correct 440 ms 174640 KB Output is correct
5 Correct 416 ms 174088 KB Output is correct
6 Correct 423 ms 174384 KB Output is correct
7 Correct 388 ms 173788 KB Output is correct
8 Correct 482 ms 178716 KB Output is correct
9 Correct 355 ms 176052 KB Output is correct
10 Correct 345 ms 174548 KB Output is correct
11 Correct 393 ms 173868 KB Output is correct
12 Correct 343 ms 173872 KB Output is correct
13 Correct 538 ms 179244 KB Output is correct
14 Correct 549 ms 179492 KB Output is correct
15 Correct 560 ms 179488 KB Output is correct
16 Correct 580 ms 179116 KB Output is correct
17 Correct 413 ms 174120 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 59484 KB Output is correct
2 Correct 15 ms 59584 KB Output is correct
3 Correct 12 ms 59484 KB Output is correct
4 Correct 13 ms 59484 KB Output is correct
5 Correct 14 ms 59692 KB Output is correct
6 Correct 12 ms 59652 KB Output is correct
7 Correct 13 ms 59480 KB Output is correct
8 Correct 12 ms 59460 KB Output is correct
9 Correct 12 ms 59484 KB Output is correct
10 Correct 18 ms 60252 KB Output is correct
11 Correct 15 ms 60292 KB Output is correct
12 Correct 16 ms 60252 KB Output is correct
13 Correct 18 ms 60400 KB Output is correct
14 Correct 16 ms 60200 KB Output is correct
15 Correct 22 ms 60248 KB Output is correct
16 Correct 455 ms 166696 KB Output is correct
17 Correct 443 ms 178992 KB Output is correct
18 Correct 423 ms 176184 KB Output is correct
19 Correct 440 ms 174640 KB Output is correct
20 Correct 416 ms 174088 KB Output is correct
21 Correct 423 ms 174384 KB Output is correct
22 Correct 388 ms 173788 KB Output is correct
23 Correct 482 ms 178716 KB Output is correct
24 Correct 355 ms 176052 KB Output is correct
25 Correct 345 ms 174548 KB Output is correct
26 Correct 393 ms 173868 KB Output is correct
27 Correct 343 ms 173872 KB Output is correct
28 Correct 538 ms 179244 KB Output is correct
29 Correct 549 ms 179492 KB Output is correct
30 Correct 560 ms 179488 KB Output is correct
31 Correct 580 ms 179116 KB Output is correct
32 Correct 413 ms 174120 KB Output is correct
33 Correct 530 ms 175668 KB Output is correct
34 Correct 296 ms 100012 KB Output is correct
35 Correct 502 ms 180036 KB Output is correct
36 Correct 518 ms 175664 KB Output is correct
37 Correct 520 ms 178988 KB Output is correct
38 Correct 456 ms 176360 KB Output is correct
39 Correct 524 ms 184556 KB Output is correct
40 Correct 542 ms 188476 KB Output is correct
41 Correct 414 ms 176856 KB Output is correct
42 Correct 365 ms 174648 KB Output is correct
43 Correct 495 ms 187420 KB Output is correct
44 Correct 450 ms 178048 KB Output is correct
45 Correct 437 ms 183600 KB Output is correct
46 Correct 421 ms 183344 KB Output is correct
47 Correct 513 ms 180012 KB Output is correct
48 Correct 488 ms 179884 KB Output is correct
49 Correct 482 ms 179540 KB Output is correct
50 Correct 509 ms 179388 KB Output is correct
51 Correct 529 ms 188448 KB Output is correct
52 Correct 521 ms 187676 KB Output is correct