oj.uz

Submission #366614

# Submission time Handle Problem Language Result Execution time Memory
366614 2021-02-14T19:33:21 Z denkendoemeer Werewolf (IOI18_werewolf) C++14
49 / 100
 641 ms 69616 KB 
#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int m,q,h[200005],mini[200005][20],maxi[200005][20],cnt;
vector<int>g[200005],sol;
bool viz[200005],na[200005],v[200005],ok;
void dfs(int nod,int t)
{
    viz[nod]=1;
    for(auto it:g[nod]){
        if (viz[it]==0 && it<=t)
            dfs(it,t);
    }
}
void dfs2(int nod,int t)
{
    na[nod]=1;
    for(auto it:g[nod]){
        if (na[it]==0 && it>=t)
            dfs2(it,t);
    }
}
void dfs3(int nod)
{
    v[nod]=1;
    mini[cnt][0]=nod;
    maxi[cnt][0]=nod;
    h[nod]=cnt;
    cnt++;
    for(auto it:g[nod])
        if (v[it]==0)
            dfs3(it);
}
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=s.size();
    int i,j;
    for(i=0;i<m;i++)
        g[x[i]].push_back(y[i]),g[y[i]].push_back(x[i]);
    if (n<=3000 && q<=3000){
        for(i=0;i<q;i++){
            ok=0;
            int j;
            for(j=0;j<n;j++)
                viz[j]=0,na[j]=0;
            dfs(e[i],r[i]);
            dfs2(s[i],l[i]);
            for(j=0;j<n;j++)
                if (viz[j] && na[j])
                    ok=1;
            sol.push_back(ok);
        }
        return sol;
    }
    for(i=0;i<n;i++)
        if (v[i]==0 && g[i].size()==1)
            dfs3(i);
    for(j=1;j<20;j++)
        for(i=0;i<n;i++){
            int auxi=min(n-1,i+(1<<(j-1)));
            mini[i][j]=min(mini[i][j-1],mini[auxi][j-1]);
            maxi[i][j]=max(maxi[i][j-1],maxi[auxi][j-1]);
        }
    for(i=0;i<q;i++){
        int a=h[s[i]],b=h[e[i]];
        if (a<b){
            for(j=19;j>=0;j--)
                if (a<n && mini[a][j]>=l[i])
                    a=a+(1<<j);
            for(j=19;j>=0;j--){
                int x=max(0,b-(1<<j)+1);
                if (maxi[x][j]<=r[i])
                    b=x-1;
            }
            if (a>=n || b==-1 || a-b>1)
                sol.push_back(1);
            else
                sol.push_back(0);
        }
        else{
            for(j=19;j>=0;j--)
                if (b<n && maxi[b][j]<=r[i])
                    b+=(1<<j);
            for(j=19;j>=0;j--){
                int x=max(0,a-(1<<j)+1);
                if (mini[x][j]>=l[i])
                    a=x-1;
            }
            if (b>=n || a==-1 || b-a>1)
                sol.push_back(1);
            else
                sol.push_back(0);
        }
    }
    return sol;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5228 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 301 ms 5612 KB Output is correct
11 Correct 176 ms 5484 KB Output is correct
12 Correct 39 ms 5612 KB Output is correct
13 Correct 313 ms 5612 KB Output is correct
14 Correct 207 ms 5484 KB Output is correct
15 Correct 260 ms 5612 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 69472 KB Output is correct
2 Correct 532 ms 69484 KB Output is correct
3 Correct 581 ms 69600 KB Output is correct
4 Correct 590 ms 69344 KB Output is correct
5 Correct 570 ms 69504 KB Output is correct
6 Correct 537 ms 69344 KB Output is correct
7 Correct 557 ms 69520 KB Output is correct
8 Correct 513 ms 69472 KB Output is correct
9 Correct 410 ms 69472 KB Output is correct
10 Correct 427 ms 69344 KB Output is correct
11 Correct 470 ms 69344 KB Output is correct
12 Correct 422 ms 69344 KB Output is correct
13 Correct 572 ms 69472 KB Output is correct
14 Correct 578 ms 69344 KB Output is correct
15 Correct 602 ms 69600 KB Output is correct
16 Correct 641 ms 69344 KB Output is correct
17 Correct 558 ms 69616 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5228 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 301 ms 5612 KB Output is correct
11 Correct 176 ms 5484 KB Output is correct
12 Correct 39 ms 5612 KB Output is correct
13 Correct 313 ms 5612 KB Output is correct
14 Correct 207 ms 5484 KB Output is correct
15 Correct 260 ms 5612 KB Output is correct
16 Correct 538 ms 69472 KB Output is correct
17 Correct 532 ms 69484 KB Output is correct
18 Correct 581 ms 69600 KB Output is correct
19 Correct 590 ms 69344 KB Output is correct
20 Correct 570 ms 69504 KB Output is correct
21 Correct 537 ms 69344 KB Output is correct
22 Correct 557 ms 69520 KB Output is correct
23 Correct 513 ms 69472 KB Output is correct
24 Correct 410 ms 69472 KB Output is correct
25 Correct 427 ms 69344 KB Output is correct
26 Correct 470 ms 69344 KB Output is correct
27 Correct 422 ms 69344 KB Output is correct
28 Correct 572 ms 69472 KB Output is correct
29 Correct 578 ms 69344 KB Output is correct
30 Correct 602 ms 69600 KB Output is correct
31 Correct 641 ms 69344 KB Output is correct
32 Correct 558 ms 69616 KB Output is correct
33 Incorrect 511 ms 63456 KB Output isn't correct
34 Halted 0 ms 0 KB -