oj.uz

Submission #431742

# Submission time Handle Problem Language Result Execution time Memory
431742 2021-06-17T14:58:33 Z Bench0310 Werewolf (IOI18_werewolf) C++17
15 / 100
 1259 ms 510208 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);
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 26 ms 43340 KB Output is correct
2 Correct 26 ms 43376 KB Output is correct
3 Correct 25 ms 43236 KB Output is correct
4 Correct 25 ms 43340 KB Output is correct
5 Correct 26 ms 43280 KB Output is correct
6 Correct 28 ms 43376 KB Output is correct
7 Correct 25 ms 43304 KB Output is correct
8 Correct 30 ms 43268 KB Output is correct
9 Correct 28 ms 43292 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 43340 KB Output is correct
2 Correct 26 ms 43376 KB Output is correct
3 Correct 25 ms 43236 KB Output is correct
4 Correct 25 ms 43340 KB Output is correct
5 Correct 26 ms 43280 KB Output is correct
6 Correct 28 ms 43376 KB Output is correct
7 Correct 25 ms 43304 KB Output is correct
8 Correct 30 ms 43268 KB Output is correct
9 Correct 28 ms 43292 KB Output is correct
10 Correct 446 ms 43796 KB Output is correct
11 Correct 312 ms 43596 KB Output is correct
12 Correct 56 ms 43652 KB Output is correct
13 Correct 384 ms 43716 KB Output is correct
14 Correct 274 ms 43680 KB Output is correct
15 Correct 310 ms 43760 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 1259 ms 510208 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 26 ms 43340 KB Output is correct
2 Correct 26 ms 43376 KB Output is correct
3 Correct 25 ms 43236 KB Output is correct
4 Correct 25 ms 43340 KB Output is correct
5 Correct 26 ms 43280 KB Output is correct
6 Correct 28 ms 43376 KB Output is correct
7 Correct 25 ms 43304 KB Output is correct
8 Correct 30 ms 43268 KB Output is correct
9 Correct 28 ms 43292 KB Output is correct
10 Correct 446 ms 43796 KB Output is correct
11 Correct 312 ms 43596 KB Output is correct
12 Correct 56 ms 43652 KB Output is correct
13 Correct 384 ms 43716 KB Output is correct
14 Correct 274 ms 43680 KB Output is correct
15 Correct 310 ms 43760 KB Output is correct
16 Runtime error 1259 ms 510208 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -