Submission #599942

#	Time	Username	Problem	Language	Result	Execution time	Memory
599942		Hanksburger	늑대인간 (IOI18_werewolf)	C++17	34 / 100	528 ms	58656 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int b[200005][18], c[200005][18], deg[200005], pos[200005], a[200005];
vector<int> adj[400005], ans;
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r)
{
    for (int i=0; i<x.size(); i++)
    {
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
        deg[x[i]]++;
        deg[y[i]]++;
    }
    for (int i=0; i<n; i++)
    {
        if (deg[i]==1)
        {
            a[0]=i;
            break;
        }
    }
    for (int i=0; i<=n-2; i++)
    {
        if (!i || adj[a[i]][0]!=a[i-1])
            a[i+1]=adj[a[i]][0];
        else
            a[i+1]=adj[a[i]][1];
        pos[a[i+1]]=i+1;
        b[i][0]=min(a[i], a[i+1]);
        c[i][0]=max(a[i], a[i+1]);
    }
    for (int i=1; i<18; i++)
    {
        for (int j=0; j<=n-2; j++)
        {
            if (j+(1<<(i-1))<=n-2)
            {
                b[j][i]=min(b[j][i-1], b[j+(1<<(i-1))][i-1]);
                c[j][i]=max(c[j][i-1], c[j+(1<<(i-1))][i-1]);
            }
            else
            {
                b[j][i]=b[j][i-1];
                c[j][i]=c[j][i-1];
            }
        }
    }
    for (int i=0; i<s.size(); i++)
    {
        int u=pos[s[i]], v=pos[e[i]];
        if (u<v)
        {
            int L=u, R=n-1;
            while (L<R)
            {
                int mid=(L+R+1)/2;
                int loog=log2(mid-L+0.1);
                if (min(b[L][loog], b[mid-(1<<loog)][loog])>=l[i])
                    L=mid;
                else
                    R=mid-1;
            }
            if (v<=L)
                ans.push_back(1);
            else
            {
                int loog=log2(v-L+0.1);
                ans.push_back(max(c[L][loog], c[v-(1<<loog)][loog])<=r[i]);
            }
        }
        else
        {
            int L=0, R=u;
            while (L<R)
            {
                int mid=(L+R)/2;
                int loog=log2(R-mid+0.1);
                if (min(b[mid][loog], b[R-(1<<loog)][loog])>=l[i])
                    R=mid;
                else
                    L=mid+1;
            }
            if (L<=v)
                ans.push_back(1);
            else
            {
                int loog=log2(L-v+0.1);
                ans.push_back(max(c[v][loog], c[L-(1<<loog)][loog])<=r[i]);
            }
        }
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:8:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for (int i=0; i<x.size(); i++)
      |                   ~^~~~~~~~~
werewolf.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i=0; i<s.size(); i++)
      |                   ~^~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51