oj.uz

Submission #431739

# Submission time Handle Problem Language Result Execution time Memory
431739 2021-06-17T14:56:50 Z Bench0310 Werewolf (IOI18_werewolf) C++17
15 / 100
 1534 ms 510252 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<set<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]=tree[2*idx];
        for(int x:tree[2*idx+1]) tree[idx].insert(x);
    }
}

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=tree[idx].lower_bound(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 25 ms 43340 KB Output is correct
2 Correct 28 ms 43376 KB Output is correct
3 Correct 25 ms 43376 KB Output is correct
4 Correct 24 ms 43340 KB Output is correct
5 Correct 24 ms 43372 KB Output is correct
6 Correct 25 ms 43284 KB Output is correct
7 Correct 25 ms 43304 KB Output is correct
8 Correct 24 ms 43288 KB Output is correct
9 Correct 24 ms 43340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 43340 KB Output is correct
2 Correct 28 ms 43376 KB Output is correct
3 Correct 25 ms 43376 KB Output is correct
4 Correct 24 ms 43340 KB Output is correct
5 Correct 24 ms 43372 KB Output is correct
6 Correct 25 ms 43284 KB Output is correct
7 Correct 25 ms 43304 KB Output is correct
8 Correct 24 ms 43288 KB Output is correct
9 Correct 24 ms 43340 KB Output is correct
10 Correct 442 ms 43688 KB Output is correct
11 Correct 316 ms 43596 KB Output is correct
12 Correct 51 ms 43612 KB Output is correct
13 Correct 379 ms 43684 KB Output is correct
14 Correct 268 ms 43784 KB Output is correct
15 Correct 331 ms 43768 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 1534 ms 510252 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 25 ms 43340 KB Output is correct
2 Correct 28 ms 43376 KB Output is correct
3 Correct 25 ms 43376 KB Output is correct
4 Correct 24 ms 43340 KB Output is correct
5 Correct 24 ms 43372 KB Output is correct
6 Correct 25 ms 43284 KB Output is correct
7 Correct 25 ms 43304 KB Output is correct
8 Correct 24 ms 43288 KB Output is correct
9 Correct 24 ms 43340 KB Output is correct
10 Correct 442 ms 43688 KB Output is correct
11 Correct 316 ms 43596 KB Output is correct
12 Correct 51 ms 43612 KB Output is correct
13 Correct 379 ms 43684 KB Output is correct
14 Correct 268 ms 43784 KB Output is correct
15 Correct 331 ms 43768 KB Output is correct
16 Runtime error 1534 ms 510252 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -