oj.uz

Submission #1085093

# Submission time Handle Problem Language Result Execution time Memory
1085093 2024-09-07T13:48:54 Z ASN49K Werewolf (IOI18_werewolf) C++14
34 / 100
 403 ms 524288 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define all(x)      x.begin(),x.end()
using namespace std;
struct query
{
    int x,y,val_l,val_r,lx,rx,ly,ry,ind;
};
const int N=200'000,UNSET=-1;
int poz[N];
namespace dsu
{
    vector<int>t,l,r;
    void init(int n) {
        t.resize(n);
        l.resize(n);
        r.resize(n);
        iota(all(t) , 0);
        for(int i=0;i<n;i++)
        {
            l[i]=r[i]=poz[i];
        }
    }
    int root(int x)
    {
        if(t[x]!=x)
        {
            t[x]=root(t[x]);
        }
        return t[x];
    }
    void unite(int x,int y)
    {
        x=root(x);
        y=root(y);
        if(x!=y)
        {
            t[y]=x;
            l[x]=min(l[x],l[y]);
            r[x]=max(r[x],r[y]);
        }
    }
}
int acm=-1;
int n,q;
vector<int>adj[N];
vector<query>querys;

bool intersect(int lx,int rx,int ly,int ry)
{
    return max(lx,ly)<=min(rx,ry);
}
void dfs(int nod,int tt)
{
    poz[nod]=++acm;
    for(auto &c:adj[nod])
    {
        if(c!=tt)
        {
            dfs(c,nod);
        }
    }
}
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;
    q=(int)L.size();
    vector<int>rez(q);
    for(int i=0;i<(int)X.size();i++)
    {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    for(int i=0;i<n;i++)
    {
        if(adj[i].size()==1)
        {
            dfs(i,UNSET);
            break;
        }
    }
    querys.resize(q);
    for(int i=0;i<q;i++)
    {
        assert(S[i]>=L[i] && E[i]<=R[i]);
        querys[i]={S[i],E[i],L[i],R[i],UNSET,UNSET,UNSET,UNSET,i};
    }
    dsu::init(n);
    sort(all(querys),[&](const query& a,const query& b){
       return a.val_l>b.val_l;
    });
    int last=n;
    for(auto &c:querys)
    {
        while(last>c.val_l)
        {
            last--;
            for(auto &v:adj[last])
            {
                if(last<v)
                {
                    dsu::unite(v,last);
                }
            }
        }
        c.lx=dsu::l[dsu::root(c.x)];
        c.rx=dsu::r[dsu::root(c.x)];
    }
    dsu::init(n);
    sort(all(querys),[&](const query& a,const query& b){
        return a.val_r<b.val_r;
    });
    last=-1;
    for(auto &c:querys)
    {
        while(last<c.val_r)
        {
            last++;
            for(auto &v:adj[last])
            {
                if(v<last)
                {
                    dsu::unite(v,last);
                }
            }
        }
        c.ly=dsu::l[dsu::root(c.y)];
        c.ry=dsu::r[dsu::root(c.y)];
    }
    for(auto &c:querys)
    {
        rez[c.ind]=intersect(c.lx,c.rx,c.ly,c.ry);
        if(c.x<c.val_l || c.y>c.val_r)
        {
            rez[c.ind]=false;
        }
    }
    return rez;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 403 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 403 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 44696 KB Output is correct
2 Correct 274 ms 44648 KB Output is correct
3 Correct 219 ms 44628 KB Output is correct
4 Correct 209 ms 44628 KB Output is correct
5 Correct 223 ms 44624 KB Output is correct
6 Correct 207 ms 44564 KB Output is correct
7 Correct 219 ms 44644 KB Output is correct
8 Correct 186 ms 44628 KB Output is correct
9 Correct 193 ms 44628 KB Output is correct
10 Correct 205 ms 44624 KB Output is correct
11 Correct 211 ms 44628 KB Output is correct
12 Correct 216 ms 44532 KB Output is correct
13 Correct 196 ms 44528 KB Output is correct
14 Correct 232 ms 44652 KB Output is correct
15 Correct 203 ms 44624 KB Output is correct
16 Correct 201 ms 44564 KB Output is correct
17 Correct 214 ms 44656 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 403 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -