oj.uz

Submission #828559

# Submission time Handle Problem Language Result Execution time Memory
828559 2023-08-17T11:09:07 Z vnm06 Werewolf (IOI18_werewolf) C++14
34 / 100
 622 ms 72308 KB 
#include<bits/stdc++.h>
#include "werewolf.h"

using namespace std;

int n, m;
int pos[200005];
vector<int> gr[200005];

void dfs(int v)
{
    for(int i=0; i<gr[v].size(); i++)
    {
        int nv=gr[v][i];
        if(pos[nv]) continue;
        pos[nv]=pos[v]+1;
        v=nv;
        dfs(v);
    }
}

vector<int> zL[200005];
vector<int> zR[200005];
vector<int> res;

int LposL[200005], LposR[200005];
int DposL[200005], DposR[200005];

int LtreeL[800005], LtreeR[800005];
int DtreeL[800005], DtreeR[800005];

void update_L(int v, int le, int ri, int pos)
{
    if(le>pos || ri<pos) return;
    if(le==ri)
    {
        LtreeL[v]=pos;
        DtreeL[v]=pos;
        return;
    }
    int mid=(le+ri)/2;
    update_L(2*v, le, mid, pos);
    update_L(2*v+1, mid+1, ri, pos);
    LtreeL[v]=min(LtreeL[2*v], LtreeL[2*v+1]);
    DtreeL[v]=max(DtreeL[2*v], DtreeL[2*v+1]);
}


void update_R(int v, int le, int ri, int pos)
{
    if(le>pos || ri<pos) return;
    if(le==ri)
    {
        LtreeR[v]=pos;
        DtreeR[v]=pos;
        return;
    }
    int mid=(le+ri)/2;
    update_R(2*v, le, mid, pos);
    update_R(2*v+1, mid+1, ri, pos);
    LtreeR[v]=min(LtreeR[2*v], LtreeR[2*v+1]);
    DtreeR[v]=max(DtreeR[2*v], DtreeR[2*v+1]);
}

int Lquery_L(int v, int le, int ri, int be, int en)
{
    if(ri<be || le>en) return n+2;
    if(be<=le && ri<=en) return LtreeL[v];
    int mid=(le+ri)/2;
    return min(Lquery_L(2*v, le, mid, be, en), Lquery_L(2*v+1, mid+1, ri, be, en));
}

int Dquery_L(int v, int le, int ri, int be, int en)
{
    if(ri<be || le>en) return -2;
    if(be<=le && ri<=en) return DtreeL[v];
    int mid=(le+ri)/2;
    return max(Dquery_L(2*v, le, mid, be, en), Dquery_L(2*v+1, mid+1, ri, be, en));
}

int Lquery_R(int v, int le, int ri, int be, int en)
{
    if(ri<be || le>en) return n+2;
    if(be<=le && ri<=en) return LtreeR[v];
    int mid=(le+ri)/2;
    return min(Lquery_R(2*v, le, mid, be, en), Lquery_R(2*v+1, mid+1, ri, be, en));
}

int Dquery_R(int v, int le, int ri, int be, int en)
{
    if(ri<be || le>en) return -2;
    if(be<=le && ri<=en) return DtreeR[v];
    int mid=(le+ri)/2;
    return max(Dquery_R(2*v, le, mid, be, en), Dquery_R(2*v+1, mid+1, ri, be, en));
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R)
{
    n=N;
    m=X.size();
    for(int i=0; i<m; i++)
    {
        gr[X[i]].push_back(Y[i]);
        gr[Y[i]].push_back(X[i]);
    }
    for(int i=0; i<n; i++)
    {
        if(gr[i].size()==1)
        {
            pos[i]=1;
            dfs(i);
            break;
        }
    }
    int q=S.size();
    for(int i=0; i<q; i++)
    {
        zL[L[i]].push_back(i);
        zR[R[i]].push_back(i);
    }
    for(int i=0; i<=800000; i++)
    {
        LtreeL[i]=n+2;
        DtreeL[i]=-2;
        LtreeR[i]=n+2;
        DtreeR[i]=-2;
    }
    for(int i=0; i<=n-1; i++)
    {
        int brid=zL[i].size();
        for(int j=0; j<brid; j++)
        {
            int id=zL[i][j];
            int ts=S[id], te=E[id];
            if(pos[ts]>pos[te]) swap(ts, te);
            LposL[id]=Lquery_L(1, 1, n, pos[ts], pos[te]);
            DposL[id]=Dquery_L(1, 1, n, pos[ts], pos[te]);
        }
        update_L(1, 1, n, pos[i]);
    }
    for(int i=n-1; i>=0; i--)
    {
        int brid=zR[i].size();
        for(int j=0; j<brid; j++)
        {
            int id=zR[i][j];
            int ts=S[id], te=E[id];
            if(pos[ts]>pos[te]) swap(ts, te);
            LposR[id]=Lquery_R(1, 1, n, pos[ts], pos[te]);
            DposR[id]=Dquery_R(1, 1, n, pos[ts], pos[te]);
        }
        update_R(1, 1, n, pos[i]);
    }
    for(int i=0; i<q; i++)
    {
        int ts=S[i], te=E[i];
        if(pos[ts]<pos[te])
        {
            if(LposL[i]>DposR[i]+1) res.push_back(1);
            else res.push_back(0);
        }
        else
        {
            if(DposL[i]<LposR[i]-1) res.push_back(1);
            else res.push_back(0);
        }
    }
    return res;
}

Compilation message

werewolf.cpp: In function 'void dfs(int)':
werewolf.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0; i<gr[v].size(); i++)
      |                  ~^~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 63792 KB Output is correct
2 Correct 546 ms 72208 KB Output is correct
3 Correct 587 ms 72308 KB Output is correct
4 Correct 622 ms 72212 KB Output is correct
5 Correct 579 ms 72204 KB Output is correct
6 Correct 569 ms 72184 KB Output is correct
7 Correct 570 ms 70092 KB Output is correct
8 Correct 542 ms 72212 KB Output is correct
9 Correct 412 ms 71200 KB Output is correct
10 Correct 461 ms 70908 KB Output is correct
11 Correct 482 ms 71108 KB Output is correct
12 Correct 449 ms 71872 KB Output is correct
13 Correct 550 ms 72212 KB Output is correct
14 Correct 612 ms 72220 KB Output is correct
15 Correct 583 ms 72176 KB Output is correct
16 Correct 567 ms 72136 KB Output is correct
17 Correct 583 ms 70028 KB Output is correct

Subtask #4
0 / 51.0

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