제출 #916552

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

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=4e5+5;
int dsu[nx], id[nx][2], idx, cnt, l[nx][2], r[nx][2], p[nx][2], res[nx];
vector<int> d[nx], a[nx], ans;
vector<pair<int, int>> c[nx];
vector<tuple<int, int, int>> eds, edt;

struct fenwick
{
    int d[nx];
    void add(int i)
    {
        while (i<nx) d[i]++, i+=(i&-i);
    }
    int find(int i)
    {
        int res=0;
        while (i>0) res+=d[i], i-=(i&-i);
        return res;
    }
} f;

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

void dfs(int u, int m)
{
    //cout<<"dfs "<<u<<'\n';
    l[u][m]=INT_MAX;
    if (d[u].empty()) return id[u][m]=l[u][m]=r[u][m]=++cnt, void();
    for (auto v:d[u]) dfs(v, m), l[u][m]=min(l[u][m], l[v][m]), r[u][m]=max(r[u][m], r[v][m]);
}

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) {
    for (int i=0; i<X.size(); i++) if (X[i]<Y[i]) swap(X[i], Y[i]);
    for (int i=0; i<X.size(); i++) eds.push_back({Y[i], 0, X[i]}), edt.push_back({X[i], 0, Y[i]});
    for (int i=0; i<S.size(); i++) eds.push_back({L[i], -1, i}), edt.push_back({R[i], 1, i});
    sort(eds.begin(), eds.end());
    reverse(eds.begin(), eds.end());
    sort(edt.begin(), edt.end());
    for (int i=0; i<2*N-1; i++) dsu[i]=i;
    idx=N;
    for (auto [u, t, v]:eds) 
    {
        //cout<<"update "<<u<<' '<<t<<' '<<v<<'\n';
        if (t==-1) p[v][0]=find(S[v]); //cout<<"find "<<v<<' '<<S[v]<<' '<<find(S[v])<<'\n';
        else if (find(u)!=find(v)) d[idx].push_back(find(u)), d[idx].push_back(find(v)), dsu[find(u)]=dsu[find(v)]=idx++; //cout<<"add edge "<<u<<' '<<v<<' '<<idx<<'\n';
    }
    dfs(idx-1, 0);
    idx=N;
    cnt=0;
    for (int i=0; i<2*N-1; i++) dsu[i]=i, d[i].clear();
    for (auto [u, t, v]:edt) 
    {
        //cout<<"update "<<u<<' '<<t<<' '<<v<<'\n';
        if (t==1) p[v][1]=find(E[v]); //cout<<"find "<<v<<' '<<S[v]<<' '<<find(S[v])<<'\n';
        else if (find(u)!=find(v)) d[idx].push_back(find(u)), d[idx].push_back(find(v)), dsu[find(u)]=dsu[find(v)]=idx++; //cout<<"add edge "<<u<<' '<<v<<' '<<idx<<'\n';
    }
    dfs(idx-1, 1);
    /*
    cout<<"id ";
    for (int i=0; i<N; i++) cout<<id[i][1]<<' ';
    cout<<'\n';
    for (int i=0; i<S.size(); i++) cout<<i<<' '<<p[i]<<' '<<l[p[i]][1]<<' '<<r[p[i]][1]<<'\n';*/
    //for (int i=0; i<S.size(); i++) cout<<"range "<<i<<' '<<l[p[i]][0]<<' '<<l[p[i]][1]<<' '<<r[p[]i][0]<<' '<<r[i][1]<<'\n';
    for (int i=0; i<S.size(); i++) c[l[p[i][0]][0]-1].push_back({-1, i}), c[r[p[i][0]][0]].push_back({1, i});
    for (int i=0; i<N; i++) a[id[i][0]].push_back(id[i][1]);
    for (int i=0; i<=N; i++)
    {
        for (auto y:a[i]) f.add(y);
        for (auto [mul, j]:c[i]) res[j]+=(f.find(r[p[j][1]][1])-f.find(l[p[j][1]][1]-1))*mul;
    }
    for (int i=0; i<S.size(); i++) ans.push_back(res[i]>0);
    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:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i=0; i<X.size(); i++) if (X[i]<Y[i]) swap(X[i], Y[i]);
      |                   ~^~~~~~~~~
werewolf.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i=0; i<X.size(); i++) eds.push_back({Y[i], 0, X[i]}), edt.push_back({X[i], 0, Y[i]});
      |                   ~^~~~~~~~~
werewolf.cpp:46:20: 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<S.size(); i++) eds.push_back({L[i], -1, i}), edt.push_back({R[i], 1, i});
      |                   ~^~~~~~~~~
werewolf.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i=0; i<S.size(); i++) c[l[p[i][0]][0]-1].push_back({-1, i}), c[r[p[i][0]][0]].push_back({1, i});
      |                   ~^~~~~~~~~
werewolf.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i=0; i<S.size(); i++) ans.push_back(res[i]>0);
      |                   ~^~~~~~~~~

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