Submission #599945

#	Time	Username	Problem	Language	Result	Execution time	Memory
599945		Hanksburger	Werewolf (IOI18_werewolf)	C++17	49 / 100	564 ms	58484 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;
bool ok[400005];
queue<int> q;
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r)
{
    if (n<=3000 && x.size()<=6000 && s.size()<=3000)
    {
        for (int i=0; i<x.size(); i++)
        {
            adj[x[i]].push_back(y[i]);
            adj[y[i]].push_back(x[i]);
            adj[n+x[i]].push_back(n+y[i]);
            adj[n+y[i]].push_back(n+x[i]);
        }
        for (int i=0; i<n; i++)
            adj[i].push_back(n+i);
        for (int i=0; i<s.size(); i++)
        {
            for (int j=0; j<n*2; j++)
                ok[j]=0;
            ok[s[i]]=1;
            q.push(s[i]);
            while (!q.empty())
            {
                int u=q.front();
                q.pop();
                for (int v:adj[u])
                {
                    if (!ok[v] && (v<n && v>=l[i] || v>=n && v<=n+r[i]))
                    {
                        ok[v]=1;
                        q.push(v);
                    }
                }
            }
            ans.push_back(ok[n+e[i]]);
        }
        return ans;
    }
    else
    {
        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:12:24: 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<x.size(); i++)
      |                       ~^~~~~~~~~
werewolf.cpp:21:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for (int i=0; i<s.size(); i++)
      |                       ~^~~~~~~~~
werewolf.cpp:33:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   33 |                     if (!ok[v] && (v<n && v>=l[i] || v>=n && v<=n+r[i]))
werewolf.cpp:46:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int i=0; i<x.size(); i++)
      |                       ~^~~~~~~~~
werewolf.cpp:87:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i=0; i<s.size(); i++)
      |                       ~^~~~~~~~~

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