oj.uz

Submission #791227

# Submission time Handle Problem Language Result Execution time Memory
791227 2023-07-23T18:29:11 Z Mouad_ouj Werewolf (IOI18_werewolf) C++17
34 / 100
 4000 ms 66508 KB 
#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
vector<vector<int> > adj;
vector<int> le,ri,ind;
int smin[800001][26],smax[800001][26];
void build(int tab[],int n)
{
	for (int x=0;x<n;x++)
	{
		smin[x][0]=tab[x];
		smax[x][0]=tab[x];
	}
	for (int y=1;y<26;y++) 
	{
		for (int x=0;(x+(1<<y)-1)<n;x++)
        {		
				smin[x][y]=min(smin[x][y-1],smin[x+(1<<(y-1))][y-1]);
				smax[x][y]=max(smax[x][y-1],smax[x+(1<<(y-1))][y-1]);
        }
	}    
}
int maxn(int l,int r)
{
	int x=(int)log2(r-l+1);
	return max(smax[l][x],smax[r-(1<<x)+1][x]);
}
int minn(int l,int r)
{
	int x=(int)log2(r-l+1);
	return min(smin[l][x],smin[r-(1<<x)+1][x]);
}
vector<int> check_validity(int n,vector<int> x,vector<int> y,vector<int> s,vector<int> e,vector<int> l,vector<int> r)
{
    int m=x.size();
    int q=s.size();
    adj.resize(n+1);
    le.resize(n+1);
    ri.resize(n+1);
    ind.resize(n+1);
    for(int a=0;a<n;a++)
    ind[a]=-1;
    for(int a=0;a<m;a++)
    {
        adj[x[a]].push_back(y[a]);
        adj[y[a]].push_back(x[a]);
    }
    int a=0,b=0;
    for(a=0;a<n;a++)
    {
        if(adj[a].size()==1)
        break;
    }
    for(b=0;b<n;b++)
    {
        if(adj[b].size()==1 && b!=a)
        break;
    }
    ind[a]=0;
    int cur=a;
    while(cur!=b)
    {
        if(ind[adj[cur][0]]==-1)
        ind[adj[cur][0]]=ind[cur]+1,cur=adj[cur][0];
        else
        ind[adj[cur][1]]=ind[cur]+1,cur=adj[cur][1];
    }
    vector<int> ans;
    ans.resize(q);
    int tab[n];
    for(int z=0;z<n;z++)
        tab[ind[z]]=z;
    build(tab,n);
    for(int z=0;z<q;z++)
    {
        int d=0;
        if(ind[e[z]]>ind[s[z]])
        {
            if(minn(ind[s[z]],ind[e[z]])>r[z] || maxn(ind[s[z]],ind[e[z]])<l[z])
            d=0;
            else
            {
                int se=ind[s[z]],re=ind[e[z]];
                while(re>se)
                {
                    int mid=(se+re+1)/2;
                    if(minn(ind[s[z]],mid)>=l[z])
                        se=mid;
                    else
                        re=mid-1;
                }
                if(tab[se]>=l[z] && tab[se]<=r[z] && maxn(se,ind[e[z]])<=r[z])
                d=1;
                else
                d=0;
            }
        }   
        else
        {
            if(minn(ind[e[z]],ind[s[z]])>r[z] || maxn(ind[e[z]],ind[s[z]])<l[z])
            d=0;
            else
            {
                int se=ind[e[z]],re=ind[s[z]];
                while(re>se)
                {
                    int mid=(se+re)/2;
                    if(minn(mid,ind[s[z]])>=l[z])
                    re=mid;
                    else
                    se=mid+1;
                }
                if(tab[se]>=l[z] && tab[se]<=r[z] && maxn(ind[e[z]],se)<=r[z])
                d=1;
                else
                d=0;
            }
        }
        ans[z]=d;
    }
    return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4083 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4083 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 65308 KB Output is correct
2 Correct 428 ms 66368 KB Output is correct
3 Correct 411 ms 66396 KB Output is correct
4 Correct 416 ms 66416 KB Output is correct
5 Correct 445 ms 66428 KB Output is correct
6 Correct 437 ms 66408 KB Output is correct
7 Correct 436 ms 66392 KB Output is correct
8 Correct 407 ms 66384 KB Output is correct
9 Correct 237 ms 66308 KB Output is correct
10 Correct 219 ms 66360 KB Output is correct
11 Correct 245 ms 66508 KB Output is correct
12 Correct 256 ms 66360 KB Output is correct
13 Correct 470 ms 66404 KB Output is correct
14 Correct 491 ms 66400 KB Output is correct
15 Correct 447 ms 66368 KB Output is correct
16 Correct 459 ms 66320 KB Output is correct
17 Correct 413 ms 66404 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4083 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -