oj.uz

Submission #600541

# Submission time Handle Problem Language Result Execution time Memory
600541 2022-07-21T04:22:00 Z Hanksburger Werewolf (IOI18_werewolf) C++17
15 / 100
 1335 ms 524288 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> child[400005], adj1[200005], adj2[200005], ql[200005], qr[200005], ans;
int p[200005], par[400005], tin[400005], tout[400005], t;
set<int> ss[400005];
int parent(int u)
{
    return (par[u]==u)?u:(par[u]=parent(par[u]));
}
void f(int u)
{
    tin[u]=(t++);
    for (int v:child[u])
        f(v);
    tout[u]=(t++);
}
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++)
    {
        int u=min(x[i], y[i]), v=max(x[i], y[i]);
        adj1[u].push_back(v);
        adj2[v].push_back(u);
    }
    for (int i=0; i<l.size(); i++)
    {
        ql[l[i]].push_back(i);
        qr[r[i]].push_back(i);
        ans.push_back(0);
    }
    for (int i=0; i<=n*2; i++)
        par[i]=i;
    int cnt=n;
    for (int i=n-1; i>=0; i--)
    {
        for (int j:adj1[i])
        {
            int a=parent(i), b=parent(j);
            if (a!=b)
            {
                child[cnt].push_back(a);
                child[cnt].push_back(b);
                par[a]=par[b]=(cnt++);
            }
        }
        for (int j:ql[i])
            p[j]=parent(s[j]);
    }
    f(cnt-1);
    for (int i=0; i<n; i++)
        ss[i].insert(tin[i]);
    for (int i=0; i<=n*2; i++)
        par[i]=i;
    cnt=n;
    for (int i=0; i<n; i++)
    {
        for (int j:adj2[i])
        {
            int a=parent(i), b=parent(j);
            if (a!=b)
            {
                ss[cnt].insert(ss[a].begin(), ss[a].end());
                ss[cnt].insert(ss[b].begin(), ss[b].end());
                par[a]=par[b]=(cnt++);
            }
        }
        for (int j:qr[i])
        {
            int x=parent(e[j]);
            auto itr=ss[x].lower_bound(tin[p[j]]);
            if (itr!=ss[x].end() && (*itr)<=tout[p[j]])
                ans[j]=1;
        }
    }
    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:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i=0; i<x.size(); i++)
      |                   ~^~~~~~~~~
werewolf.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i=0; i<l.size(); i++)
      |                   ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47436 KB Output is correct
2 Correct 26 ms 47276 KB Output is correct
3 Correct 22 ms 47408 KB Output is correct
4 Correct 22 ms 47292 KB Output is correct
5 Correct 26 ms 47392 KB Output is correct
6 Correct 22 ms 47444 KB Output is correct
7 Correct 24 ms 47444 KB Output is correct
8 Correct 23 ms 47304 KB Output is correct
9 Correct 22 ms 47552 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47436 KB Output is correct
2 Correct 26 ms 47276 KB Output is correct
3 Correct 22 ms 47408 KB Output is correct
4 Correct 22 ms 47292 KB Output is correct
5 Correct 26 ms 47392 KB Output is correct
6 Correct 22 ms 47444 KB Output is correct
7 Correct 24 ms 47444 KB Output is correct
8 Correct 23 ms 47304 KB Output is correct
9 Correct 22 ms 47552 KB Output is correct
10 Correct 273 ms 157860 KB Output is correct
11 Correct 186 ms 116484 KB Output is correct
12 Correct 33 ms 50920 KB Output is correct
13 Correct 537 ms 259480 KB Output is correct
14 Correct 520 ms 259532 KB Output is correct
15 Correct 185 ms 109184 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1335 ms 429528 KB Output is correct
2 Runtime error 1231 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47436 KB Output is correct
2 Correct 26 ms 47276 KB Output is correct
3 Correct 22 ms 47408 KB Output is correct
4 Correct 22 ms 47292 KB Output is correct
5 Correct 26 ms 47392 KB Output is correct
6 Correct 22 ms 47444 KB Output is correct
7 Correct 24 ms 47444 KB Output is correct
8 Correct 23 ms 47304 KB Output is correct
9 Correct 22 ms 47552 KB Output is correct
10 Correct 273 ms 157860 KB Output is correct
11 Correct 186 ms 116484 KB Output is correct
12 Correct 33 ms 50920 KB Output is correct
13 Correct 537 ms 259480 KB Output is correct
14 Correct 520 ms 259532 KB Output is correct
15 Correct 185 ms 109184 KB Output is correct
16 Correct 1335 ms 429528 KB Output is correct
17 Runtime error 1231 ms 524288 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -