oj.uz

Submission #431682

# Submission time Handle Problem Language Result Execution time Memory
431682 2021-06-17T14:28:32 Z Bench0310 Werewolf (IOI18_werewolf) C++17
15 / 100
 797 ms 43280 KB 
#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;
typedef long long ll;

const int N=200005;
int n,q;
vector<int> v[N];

vector<int> solve_small(vector<int> ns,vector<int> ne,vector<int> nl,vector<int> nr)
{
    vector<int> res(q,0);
    for(int o=0;o<q;o++)
    {
        int s=ns[o];
        int e=ne[o];
        int l=nl[o];
        int r=nr[o];
        vector<array<int,2>> dp(n,{0,0});
        queue<array<int,2>> b;
        auto add=[&](int a,int t)
        {
            if(dp[a][t]==0)
            {
                dp[a][t]=1;
                b.push({a,t});
            }
        };
        add(s,0);
        while(!b.empty())
        {
            auto [a,t]=b.front();
            b.pop();
            if(l<=a&&a<=r&&t==0) add(a,1);
            for(int to:v[a])
            {
                if(t==0&&to>=l) add(to,0);
                if(t==1&&to<=r) add(to,1);
            }
        }
        res[o]=dp[e][1];
    }
    return res;
}

struct ST
{
    vector<int> tree;
    ST()
    {
        tree.assign(4*(n+5),0);
    }
    void update(int idx,int l,int r,int pos,int val)
    {
        if(l==r) tree[idx]=val;
        else
        {
            int m=(l+r)/2;
            if(pos<=m) update(2*idx,l,m,pos,val);
            else update(2*idx+1,m+1,r,pos,val);
            tree[idx]=tree[2*idx]+tree[2*idx+1];
        }
    }
    void upd(int pos,int val){update(1,0,n-1,pos,val);}
    int descend(int idx,int l,int r,int ql,int qr,int t) //0-l,1-r
    {
        if(ql>qr||tree[idx]==0) return -1;
        if(l==r) return l;
        int m=(l+r)/2;
        if(t==0)
        {
            int x=descend(2*idx,l,m,ql,min(qr,m),t);
            if(x!=-1) return x;
            else return descend(2*idx+1,m+1,r,max(ql,m+1),qr,t);
        }
        else
        {
            int x=descend(2*idx+1,m+1,r,max(ql,m+1),qr,t);
            if(x!=-1) return x;
            else return descend(2*idx,l,m,ql,min(qr,m),t);
        }
    }
    int dsn(int ql,int qr,int t){return descend(1,0,n-1,ql,qr,t);}
};

vector<int> solve_line(vector<int> ns,vector<int> ne,vector<int> nl,vector<int> nr)
{
    vector<int> pos(n,-1);
    int src=-1;
    for(int i=0;i<n;i++) if(v[i].size()==1) src=i;
    int p=0;
    while(pos[src]==-1)
    {
        pos[src]=p++;
        for(int to:v[src])
        {
            if(pos[to]==-1)
            {
                src=to;
                break;
            }
        }
    }
    vector<int> badhuman(n,-1);
    vector<int> badwolf(n,-1);
    vector<int> ord[n];
    for(int i=0;i<q;i++)
    {
        int l=nl[i];
        ord[l].push_back(i);
    }
    ST one;
    for(int i=0;i<n;i++)
    {
        for(int a:ord[i])
        {
            int s=ns[a];
            int e=ne[a];
            if(pos[s]<pos[e]) badhuman[a]=one.dsn(pos[s],pos[e],0);
            else badhuman[a]=one.dsn(pos[e],pos[s],1);
        }
        one.upd(pos[i],1);
    }
    for(int i=0;i<n;i++) ord[i].clear();
    for(int i=0;i<q;i++)
    {
        int r=nr[i];
        ord[r].push_back(i);
    }
    ST two;
    for(int i=n-1;i>=0;i--)
    {
        for(int a:ord[i])
        {
            int s=ns[a];
            int e=ne[a];
            if(pos[s]<pos[e]) badwolf[a]=two.dsn(pos[s],pos[e],1);
            else badwolf[a]=two.dsn(pos[e],pos[s],0);
        }
        two.upd(pos[i],1);
    }
    vector<int> res(q,0);
    for(int i=0;i<q;i++)
    {
        int s=ns[i];
        int e=ne[i];
        if(badhuman[i]==-1||badwolf[i]==-1) res[i]=1;
        else if(pos[s]<pos[e]) res[i]=(badwolf[i]<badhuman[i]);
        else res[i]=(badhuman[i]<badwolf[i]);
    }
    return res;
}

vector<int> check_validity(int nn,vector<int> nx,vector<int> ny,vector<int> ns,vector<int> ne,vector<int> nl,vector<int> nr)
{
    n=nn;
    int m=nx.size();
    q=ns.size();
    for(int i=0;i<m;i++)
    {
        v[nx[i]].push_back(ny[i]);
        v[ny[i]].push_back(nx[i]);
    }
    if(n<=3000&&m<=6000&&q<=3000) return solve_small(ns,ne,nl,nr);
    else return solve_line(ns,ne,nl,nr);
}

//int main()
//{
//    
//    return 0;
//}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 5 ms 4892 KB Output is correct
6 Correct 4 ms 4996 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 442 ms 5420 KB Output is correct
11 Correct 299 ms 5444 KB Output is correct
12 Correct 31 ms 5444 KB Output is correct
13 Correct 362 ms 5416 KB Output is correct
14 Correct 253 ms 5408 KB Output is correct
15 Correct 294 ms 5524 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 797 ms 43280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 5 ms 4892 KB Output is correct
6 Correct 4 ms 4996 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 442 ms 5420 KB Output is correct
11 Correct 299 ms 5444 KB Output is correct
12 Correct 31 ms 5444 KB Output is correct
13 Correct 362 ms 5416 KB Output is correct
14 Correct 253 ms 5408 KB Output is correct
15 Correct 294 ms 5524 KB Output is correct
16 Incorrect 797 ms 43280 KB Output isn't correct
17 Halted 0 ms 0 KB -