oj.uz

Submission #431746

# Submission time Handle Problem Language Result Execution time Memory
431746 2021-06-17T15:00:33 Z Bench0310 Werewolf (IOI18_werewolf) C++17
15 / 100
 861 ms 164508 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> tmpini(N,0);
vector<int> tree[4*N];

void build(int idx,int l,int r)
{
    if(l==r) tree[idx]={tmpini[l]};
    else
    {
        int m=(l+r)/2;
        build(2*idx,l,m);
        build(2*idx+1,m+1,r);
        tree[idx].reserve(r-l+1);
        merge(tree[2*idx].begin(),tree[2*idx].end(),tree[2*idx+1].begin(),tree[2*idx+1].end(),back_inserter(tree[idx]));
    }
}

bool query(int idx,int l,int r,int ql,int qr,int one,int two)
{
    if(ql>qr) return 0;
    if(l==ql&&r==qr)
    {
        auto it=lower_bound(tree[idx].begin(),tree[idx].end(),one);
        return (it!=tree[idx].end()&&(*it)<=r);
    }
    int m=(l+r)/2;
    return (query(2*idx,l,m,ql,min(qr,m),one,two)||query(2*idx+1,m+1,r,max(ql,m+1),qr,one,two));
}

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;
    vector<int> h(n,-1);
    while(pos[src]==-1)
    {
//        cerr << src << " ";
        h[p]=src;
        pos[src]=p++;
        for(int to:v[src])
        {
            if(pos[to]==-1)
            {
                src=to;
                break;
            }
        }
    }
//    cerr << endl;
    tmpini=h;
    build(1,0,n-1);
    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++)
    {
//        cerr << i << ": " << badhuman[i] << " " << badwolf[i] << endl;
        int l=nl[i];
        int r=nr[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]&&query(1,0,n-1,badwolf[i]+1,badhuman[i]-1,l,r)==1);
        else res[i]=(badhuman[i]<badwolf[i]&&query(1,0,n-1,badhuman[i]+1,badwolf[i]-1,l,r)==1);
    }
    return res;
}

void ini(int nn,vector<int> nx,vector<int> ny,vector<int> ns)
{
    
    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]);
    }
}

void clean()
{
    for(int i=0;i<n;i++) v[i].clear();
}

vector<int> check_validity(int nn,vector<int> nx,vector<int> ny,vector<int> ns,vector<int> ne,vector<int> nl,vector<int> nr)
{
    ini(nn,nx,ny,ns);
    int m=nx.size();
    if(n<=3000&&m<=6000&&q<=3000) return solve_small(ns,ne,nl,nr);
    else return solve_line(ns,ne,nl,nr);
}

//int main()
//{
//    mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
//    auto rng=[&](int l,int r)->int{return uniform_int_distribution<int>(l,r)(gen);};
//    auto rng_shuffle=[&](auto &t){shuffle(t.begin(),t.end(),gen);};
//    while(1)
//    {
//        n=rng(2,4);
//        int m=n-1;
//        q=1;
//        vector<int> x(m);
//        vector<int> y(m);
//        vector<int> ord(n);
//        for(int i=0;i<n;i++) ord[i]=i;
//        rng_shuffle(ord);
//        for(int i=0;i<n-1;i++)
//        {
//            x[i]=ord[i];
//            y[i]=ord[i+1];
//        }
//        vector<int> s(q);
//        vector<int> e(q);
//        vector<int> l(q);
//        vector<int> r(q);
//        for(int i=0;i<q;i++)
//        {
//            s[i]=rng(0,n-2);
//            e[i]=rng(s[i]+1,n-1);
//            l[i]=rng(0,s[i]);
//            r[i]=rng(e[i],n-1);
//        }
//        ini(n,x,y,s);
//        vector<int> one=solve_small(s,e,l,r);
//        vector<int> two=solve_line(s,e,l,r);
//        if(one!=two)
//        {
//            cout << "WA" << endl;
//            cout << n << " " << m << " " << q << endl;
//            for(int i=0;i<m;i++) cout << x[i] << " " << y[i] << endl;
//            for(int i=0;i<q;i++) cout << s[i] << " " << e[i] << " " << l[i] << " " << r[i] << endl;
//            cout << "|Received| ";
//            for(int i=0;i<q;i++) cout << two[i];
//            cout << endl;
//            cout << "|Expected| ";
//            for(int i=0;i<q;i++) cout << one[i];
//            cout << endl;
//            break;
//        }
//        else cout << "OK" << endl;
//        clean();
//    }
//    return 0;
//}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24548 KB Output is correct
2 Correct 18 ms 24524 KB Output is correct
3 Correct 15 ms 24524 KB Output is correct
4 Correct 15 ms 24480 KB Output is correct
5 Correct 16 ms 24524 KB Output is correct
6 Correct 15 ms 24572 KB Output is correct
7 Correct 15 ms 24540 KB Output is correct
8 Correct 15 ms 24524 KB Output is correct
9 Correct 17 ms 24508 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24548 KB Output is correct
2 Correct 18 ms 24524 KB Output is correct
3 Correct 15 ms 24524 KB Output is correct
4 Correct 15 ms 24480 KB Output is correct
5 Correct 16 ms 24524 KB Output is correct
6 Correct 15 ms 24572 KB Output is correct
7 Correct 15 ms 24540 KB Output is correct
8 Correct 15 ms 24524 KB Output is correct
9 Correct 17 ms 24508 KB Output is correct
10 Correct 436 ms 24900 KB Output is correct
11 Correct 310 ms 24892 KB Output is correct
12 Correct 39 ms 24880 KB Output is correct
13 Correct 380 ms 24904 KB Output is correct
14 Correct 256 ms 24880 KB Output is correct
15 Correct 336 ms 24964 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 861 ms 164508 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24548 KB Output is correct
2 Correct 18 ms 24524 KB Output is correct
3 Correct 15 ms 24524 KB Output is correct
4 Correct 15 ms 24480 KB Output is correct
5 Correct 16 ms 24524 KB Output is correct
6 Correct 15 ms 24572 KB Output is correct
7 Correct 15 ms 24540 KB Output is correct
8 Correct 15 ms 24524 KB Output is correct
9 Correct 17 ms 24508 KB Output is correct
10 Correct 436 ms 24900 KB Output is correct
11 Correct 310 ms 24892 KB Output is correct
12 Correct 39 ms 24880 KB Output is correct
13 Correct 380 ms 24904 KB Output is correct
14 Correct 256 ms 24880 KB Output is correct
15 Correct 336 ms 24964 KB Output is correct
16 Runtime error 861 ms 164508 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -