oj.uz

Submission #610822

# Submission time Handle Problem Language Result Execution time Memory
610822 2022-07-28T15:17:25 Z azberjibiou Werewolf (IOI18_werewolf) C++17
100 / 100
 723 ms 80700 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fir first
#define sec second
using namespace std;
typedef struct qry{
    int s, e, l, r, idx;
}qry;
const int mxN=200200;
int N, M, Q;
qry A[mxN];
vector <pii> E;
vector <int> adj[mxN], adjr[mxN], adjl[mxN];
int inl[mxN], outl[mxN], inr[mxN], outr[mxN], invr[mxN];
int eidx;
vector <pii> cont[mxN];
vector <int> ans;
int par[mxN];
void init_uf(){for(int i=0;i<N;i++) par[i]=i;}
int findpar(int a){return (par[a]==a ? a : par[a]=findpar(par[a]));}
void onion(int a, int b, bool inv)
{
    int p=findpar(a), q=findpar(b);
    if(inv) par[max(p, q)]=min(p, q);
    else    par[min(p, q)]=max(p, q);
}
void dfsr(int now)
{
    inr[now]=eidx;
    for(int nxt : adjr[now])    dfsr(nxt);
    outr[now]=eidx++;
    invr[outr[now]]=now;
}
void dfsl(int now)
{
    inl[now]=eidx;
    for(int nxt : adjl[now])    dfsl(nxt);
    outl[now]=eidx++;
}
int seg[4*mxN];
void upd(int idx, int s, int e, int pos)
{
    if(s==e)
    {
        seg[idx]++;
        return;
    }
    int mid=(s+e)/2;
    if(pos<=mid)    upd(2*idx, s, mid, pos);
    else    upd(2*idx+1, mid+1, e, pos);
    seg[idx]++;
}
int solv(int idx, int s1, int e1, int s2, int e2)
{
    if(s1>e2 || s2>e1)  return 0;
    if(s2<=s1 && e1<=e2)    return seg[idx];
    int mid=(s1+e1)/2;
    return solv(2*idx, s1, mid, s2, e2)+solv(2*idx+1, mid+1, e1, s2, e2);
}
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    N=n;
    M=X.size();
    Q = S.size();
    ans.resize(Q);
    for(int i=0;i<Q;i++)
    {
        A[i].s=S[i], A[i].e=E[i], A[i].l=L[i], A[i].r=R[i], A[i].idx=i;
    }
    for(int i=0;i<M;i++)    adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
    init_uf();
    sort(A, A+Q, [](qry a, qry b){return a.r<b.r;});
    int cur=0;
    for(int i=0;i<Q;i++)
    {
        while(cur<A[i].r)
        {
            for(int ele : adj[cur+1])   if(ele<=cur)    onion(ele, cur+1, false);
            cur++;
        }
        if(A[i].e>A[i].r)   A[i].e=-1;
        else    A[i].e=findpar(A[i].e);
    }
    init_uf();
    sort(A, A+Q, [](qry a, qry b){return a.l>b.l;});
    cur=N-1;
    for(int i=0;i<Q;i++)
    {
        while(cur>A[i].l)
        {
            for(int ele : adj[cur-1])   if(ele>=cur)    onion(ele, cur-1, true);
            cur--;
        }
        if(A[i].s<A[i].l)   A[i].s=-1;
        else    A[i].s=findpar(A[i].s);
    }
    sort(A, A+Q, [](qry a, qry b){return a.idx<b.idx;});
    init_uf();
    for(int i=1;i<N;i++)    for(int ele : adj[i])   if(ele<i && findpar(ele)!=i)
    {
        adjr[i].push_back(findpar(ele));
        onion(ele, i, false);
    }
    init_uf();
    for(int i=N-1;i>=0;i--) for(int ele : adj[i])   if(ele>i && findpar(ele)!=i)
    {
        adjl[i].push_back(findpar(ele));
        onion(ele, i, true);
    }
    eidx=1;
    dfsr(N-1);
    eidx=1;
    dfsl(0);
    for(int i=0;i<Q;i++)
    {
        if(A[i].s==-1 || A[i].e==-1)    continue;
        cont[inr[A[i].e]-1].emplace_back(i, -1);
        cont[outr[A[i].e]].emplace_back(i, 1);
    }
    for(int i=1;i<=N;i++)
    {
        int now=invr[i];
        upd(1, 1, N, outl[now]);
        for(pii ele : cont[i])
        {
            pii rng=pii(inl[A[ele.fir].s], outl[A[ele.fir].s]);
            ans[ele.fir]+=solv(1, 1, N, rng.fir, rng.sec)*ele.sec;
        }
    }
    for(int i=0;i<Q;i++)
    {
        if(A[i].s==-1 || A[i].e==-1)    ans[i]=0;
        else if(ans[i]!=0)  ans[i]=1;
    }
    return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19128 KB Output is correct
2 Correct 10 ms 19128 KB Output is correct
3 Correct 15 ms 19088 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 10 ms 19120 KB Output is correct
6 Correct 10 ms 19156 KB Output is correct
7 Correct 11 ms 19100 KB Output is correct
8 Correct 10 ms 19156 KB Output is correct
9 Correct 10 ms 19144 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19128 KB Output is correct
2 Correct 10 ms 19128 KB Output is correct
3 Correct 15 ms 19088 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 10 ms 19120 KB Output is correct
6 Correct 10 ms 19156 KB Output is correct
7 Correct 11 ms 19100 KB Output is correct
8 Correct 10 ms 19156 KB Output is correct
9 Correct 10 ms 19144 KB Output is correct
10 Correct 17 ms 19832 KB Output is correct
11 Correct 17 ms 19932 KB Output is correct
12 Correct 16 ms 19796 KB Output is correct
13 Correct 14 ms 20068 KB Output is correct
14 Correct 14 ms 20036 KB Output is correct
15 Correct 23 ms 19924 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 68164 KB Output is correct
2 Correct 720 ms 71148 KB Output is correct
3 Correct 624 ms 68736 KB Output is correct
4 Correct 598 ms 67764 KB Output is correct
5 Correct 592 ms 67776 KB Output is correct
6 Correct 578 ms 68268 KB Output is correct
7 Correct 545 ms 67136 KB Output is correct
8 Correct 621 ms 71628 KB Output is correct
9 Correct 512 ms 69004 KB Output is correct
10 Correct 441 ms 66696 KB Output is correct
11 Correct 495 ms 67484 KB Output is correct
12 Correct 510 ms 67324 KB Output is correct
13 Correct 520 ms 76708 KB Output is correct
14 Correct 496 ms 76604 KB Output is correct
15 Correct 521 ms 76648 KB Output is correct
16 Correct 514 ms 77336 KB Output is correct
17 Correct 547 ms 67240 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19128 KB Output is correct
2 Correct 10 ms 19128 KB Output is correct
3 Correct 15 ms 19088 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 10 ms 19120 KB Output is correct
6 Correct 10 ms 19156 KB Output is correct
7 Correct 11 ms 19100 KB Output is correct
8 Correct 10 ms 19156 KB Output is correct
9 Correct 10 ms 19144 KB Output is correct
10 Correct 17 ms 19832 KB Output is correct
11 Correct 17 ms 19932 KB Output is correct
12 Correct 16 ms 19796 KB Output is correct
13 Correct 14 ms 20068 KB Output is correct
14 Correct 14 ms 20036 KB Output is correct
15 Correct 23 ms 19924 KB Output is correct
16 Correct 619 ms 68164 KB Output is correct
17 Correct 720 ms 71148 KB Output is correct
18 Correct 624 ms 68736 KB Output is correct
19 Correct 598 ms 67764 KB Output is correct
20 Correct 592 ms 67776 KB Output is correct
21 Correct 578 ms 68268 KB Output is correct
22 Correct 545 ms 67136 KB Output is correct
23 Correct 621 ms 71628 KB Output is correct
24 Correct 512 ms 69004 KB Output is correct
25 Correct 441 ms 66696 KB Output is correct
26 Correct 495 ms 67484 KB Output is correct
27 Correct 510 ms 67324 KB Output is correct
28 Correct 520 ms 76708 KB Output is correct
29 Correct 496 ms 76604 KB Output is correct
30 Correct 521 ms 76648 KB Output is correct
31 Correct 514 ms 77336 KB Output is correct
32 Correct 547 ms 67240 KB Output is correct
33 Correct 632 ms 69480 KB Output is correct
34 Correct 316 ms 53016 KB Output is correct
35 Correct 664 ms 71612 KB Output is correct
36 Correct 654 ms 70516 KB Output is correct
37 Correct 660 ms 72232 KB Output is correct
38 Correct 676 ms 71092 KB Output is correct
39 Correct 522 ms 79784 KB Output is correct
40 Correct 666 ms 78824 KB Output is correct
41 Correct 610 ms 70224 KB Output is correct
42 Correct 510 ms 68796 KB Output is correct
43 Correct 723 ms 77836 KB Output is correct
44 Correct 612 ms 71508 KB Output is correct
45 Correct 570 ms 80700 KB Output is correct
46 Correct 575 ms 80520 KB Output is correct
47 Correct 505 ms 77888 KB Output is correct
48 Correct 519 ms 77744 KB Output is correct
49 Correct 590 ms 77888 KB Output is correct
50 Correct 544 ms 77684 KB Output is correct
51 Correct 645 ms 78696 KB Output is correct
52 Correct 619 ms 78520 KB Output is correct