제출 #1333469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1333469		activedeltorre	늑대인간 (IOI18_werewolf)	C++20	0 / 100	233 ms	49240 KiB

werewolf

#include "werewolf.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
//#include "werewolf.h"
using namespace std;
int sef[300005];
int cnt[300005];
int x[600005];
int y[600005];
vector<int>adj[200005];
vector<int>tree1[200005];
vector<int>tree2[200005];
int find(int a)
{
    if(sef[a]==a)
    {
        return a;
    }
    return sef[a]=find(sef[a]);
}
void merge(int a,int b)
{
    a=find(a);
    b=find(b);
    sef[b]=a;
}
int in1[200005];
int out1[200005];
int timp1=0;
int dfs1(int curr)
{
    timp1++;
    in1[curr]=timp1;
    for(auto k:tree1[curr])
    {
        dfs1(k);
    }
    out1[curr]=timp1;
}
int in2[200005];
int out2[200005];
int timp2=0;
int dfs2(int curr)
{
    timp2++;
    in2[curr]=timp2;
    for(auto k:tree2[curr])
    {
        dfs2(k);
    }
    out2[curr]=timp2;
}
int st1[200005];
int st2[200005];
int dr1[200005];
int dr2[200005];
int can1[200005];
int can2[200005];
vector<pair<int,int>>qu1[200005];
vector<pair<int,int>>qu2[200005];
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    int n=N,dim;
    int m=X.size();
    int q=S.size();
    vector<int>rasp;
    for(int i=0;i<m;i++)
    {
        x[i]=X[i];
        y[i]=Y[i];
        if(X[i]>Y[i])
        {
            swap(x[i],y[i]);
        }
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    for(int i=0;i<q;i++)
    {
        qu1[R[i]].push_back({E[i],i});
        qu2[L[i]].push_back({S[i],i});
    }
    for(int i=0;i<n;i++)
    {
        sef[i]=i;
    }
    for(int i=0;i<n;i++)
    {
        for(auto j:adj[i])
        {
            if(j<i)
            {
                if(find(i)!=find(j))
                {
                    //cout<<"muhc "<<i<<" "<<find(j)<<'\n';
                    tree1[i].push_back(find(j));
                    merge(i,j);
                }
            }
        }
        for(auto j:qu1[i])
        {
            can1[j.second]=find(j.first);
            //cout<<"query"<<" "<<j.second<<" "<<j.first<<" "<<can1[j.second]<<'\n';
        }
    }
    dfs1(n-1);
    for(int i=0;i<n;i++)
    {
        sef[i]=i;
    }
    for(int i=n-1;i>=0;i--)
    {
        for(auto j:adj[i])
        {
            if(j>i)
            {
                if(find(i)!=find(j))
                {
                    //cout<<"muhc "<<i<<" "<<find(j)<<'\n';
                    tree2[i].push_back(find(j));
                    merge(i,j);
                }
            }
        }
        for(auto j:qu2[i])
        {
            can2[j.second]=find(j.first);
            //cout<<"query"<<" "<<j.second<<" "<<j.first<<" "<<can1[j.second]<<'\n';
        }
    }
    dfs2(0);
    vector<int>rez;
    for(int i=0;i<q;i++)
    {
        //cout<<in1[can1[i]]<<" "<<out1[can1[i]]<<" "<<in2[can2[i]]<<" "<<out2[can2[i]]<<'\n';
        int gas=0;
        for(int j=0;j<n;j++)
        {
            if(in1[can1[i]]<=in1[j] && in1[j]<=out1[can1[i]] && in2[can2[i]]<=in2[j] && in2[j]<=out2[can2[i]])
            {
                gas=1;
                break;
            }
        }
        rez.push_back(gas);
    }
    return rez;
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'int dfs1(int)':
werewolf.cpp:41:1: warning: no return statement in function returning non-void [-Wreturn-type]
   41 | }
      | ^
werewolf.cpp: In function 'int dfs2(int)':
werewolf.cpp:54:1: warning: no return statement in function returning non-void [-Wreturn-type]
   54 | }
      | ^

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