oj.uz

Submission #599942

# Submission time Handle Problem Language Result Execution time Memory
599942 2022-07-20T10:14:02 Z Hanksburger Werewolf (IOI18_werewolf) C++17
34 / 100
 528 ms 58656 KB 
#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

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.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 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 469 ms 57872 KB Output is correct
2 Correct 512 ms 58588 KB Output is correct
3 Correct 491 ms 58452 KB Output is correct
4 Correct 484 ms 58656 KB Output is correct
5 Correct 485 ms 58468 KB Output is correct
6 Correct 493 ms 58444 KB Output is correct
7 Correct 487 ms 58432 KB Output is correct
8 Correct 412 ms 58500 KB Output is correct
9 Correct 362 ms 58560 KB Output is correct
10 Correct 365 ms 58508 KB Output is correct
11 Correct 372 ms 58420 KB Output is correct
12 Correct 346 ms 58532 KB Output is correct
13 Correct 528 ms 58456 KB Output is correct
14 Correct 522 ms 58560 KB Output is correct
15 Correct 506 ms 58592 KB Output is correct
16 Correct 492 ms 58584 KB Output is correct
17 Correct 512 ms 58552 KB Output is correct

Subtask #4
0 / 51.0

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