제출 #600542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600542		Hanksburger	늑대인간 (IOI18_werewolf)	C++17	100 / 100	723 ms	158564 KiB

werewolf

#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]);
        par[i]=i;
    }
    for (int i=0; i<n; i++)
    {
        for (int j:adj2[i])
        {
            int a=parent(i), b=parent(j);
            if (a!=b)
            {
                if (ss[a].size()>ss[b].size())
                    swap(a, b);
                ss[b].insert(ss[a].begin(), ss[a].end());
                par[a]=b;
            }
        }
        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;
}

컴파일 시 표준 에러 (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: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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51