oj.uz

Submission #431769

# Submission time Handle Problem Language Result Execution time Memory
431769 2021-06-17T15:12:53 Z Bench0310 Werewolf (IOI18_werewolf) C++17
49 / 100
 797 ms 96060 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)
{
//    cout << "[" << idx << "," << l << "," << r << "," << ql << "," << qr << "," << one << "," << two << "]" << endl;
    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)<=two);
    }
    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(q,-1);
    vector<int> badwolf(q,-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();
    for(int i=0;i<4*(n+5);i++) tree[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,1000);
//        int m=n-1;
//        q=1000;
//        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 24524 KB Output is correct
2 Correct 18 ms 24488 KB Output is correct
3 Correct 17 ms 24476 KB Output is correct
4 Correct 19 ms 24480 KB Output is correct
5 Correct 18 ms 24572 KB Output is correct
6 Correct 18 ms 24524 KB Output is correct
7 Correct 18 ms 24576 KB Output is correct
8 Correct 19 ms 24564 KB Output is correct
9 Correct 19 ms 24476 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24524 KB Output is correct
2 Correct 18 ms 24488 KB Output is correct
3 Correct 17 ms 24476 KB Output is correct
4 Correct 19 ms 24480 KB Output is correct
5 Correct 18 ms 24572 KB Output is correct
6 Correct 18 ms 24524 KB Output is correct
7 Correct 18 ms 24576 KB Output is correct
8 Correct 19 ms 24564 KB Output is correct
9 Correct 19 ms 24476 KB Output is correct
10 Correct 436 ms 25060 KB Output is correct
11 Correct 311 ms 24856 KB Output is correct
12 Correct 43 ms 24836 KB Output is correct
13 Correct 383 ms 24928 KB Output is correct
14 Correct 268 ms 24908 KB Output is correct
15 Correct 344 ms 25048 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 797 ms 87660 KB Output is correct
2 Correct 634 ms 95828 KB Output is correct
3 Correct 619 ms 95948 KB Output is correct
4 Correct 634 ms 95836 KB Output is correct
5 Correct 644 ms 95904 KB Output is correct
6 Correct 780 ms 95828 KB Output is correct
7 Correct 638 ms 94324 KB Output is correct
8 Correct 545 ms 95816 KB Output is correct
9 Correct 555 ms 95176 KB Output is correct
10 Correct 589 ms 95568 KB Output is correct
11 Correct 575 ms 95568 KB Output is correct
12 Correct 614 ms 95628 KB Output is correct
13 Correct 591 ms 95824 KB Output is correct
14 Correct 622 ms 95808 KB Output is correct
15 Correct 658 ms 95744 KB Output is correct
16 Correct 655 ms 95832 KB Output is correct
17 Correct 670 ms 94480 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24524 KB Output is correct
2 Correct 18 ms 24488 KB Output is correct
3 Correct 17 ms 24476 KB Output is correct
4 Correct 19 ms 24480 KB Output is correct
5 Correct 18 ms 24572 KB Output is correct
6 Correct 18 ms 24524 KB Output is correct
7 Correct 18 ms 24576 KB Output is correct
8 Correct 19 ms 24564 KB Output is correct
9 Correct 19 ms 24476 KB Output is correct
10 Correct 436 ms 25060 KB Output is correct
11 Correct 311 ms 24856 KB Output is correct
12 Correct 43 ms 24836 KB Output is correct
13 Correct 383 ms 24928 KB Output is correct
14 Correct 268 ms 24908 KB Output is correct
15 Correct 344 ms 25048 KB Output is correct
16 Correct 797 ms 87660 KB Output is correct
17 Correct 634 ms 95828 KB Output is correct
18 Correct 619 ms 95948 KB Output is correct
19 Correct 634 ms 95836 KB Output is correct
20 Correct 644 ms 95904 KB Output is correct
21 Correct 780 ms 95828 KB Output is correct
22 Correct 638 ms 94324 KB Output is correct
23 Correct 545 ms 95816 KB Output is correct
24 Correct 555 ms 95176 KB Output is correct
25 Correct 589 ms 95568 KB Output is correct
26 Correct 575 ms 95568 KB Output is correct
27 Correct 614 ms 95628 KB Output is correct
28 Correct 591 ms 95824 KB Output is correct
29 Correct 622 ms 95808 KB Output is correct
30 Correct 658 ms 95744 KB Output is correct
31 Correct 655 ms 95832 KB Output is correct
32 Correct 670 ms 94480 KB Output is correct
33 Incorrect 567 ms 96060 KB Output isn't correct
34 Halted 0 ms 0 KB -