제출 #759554

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

werewolf

#include "werewolf.h"
#include <iostream>
#include <vector>
#define f first
#define s second
using namespace std;
 
int n, m, q, p[200010], id[200010], pmax[600010][21], pmin[600010][21], vmax[600010], vmin[600010], mxsz, mnsz, cnt;
pair<int,int> rmax[600010], rmin[600010];
vector<int> edge[200010], maxx[600010], minn[600010], node[800010], ps[800010];
 
int dsu(int u) {
    if (p[u] == u) return u;
    return (p[u] = dsu(p[u]));
}
 
void buildmax(int u) {
    int v = pmax[u][0];
    for (int i = 1; i <= 20; i++) {
        if (v == -1) break;
        pmax[u][i] = pmax[v][i-1];
        v = pmax[u][i];
    }
    if (maxx[u].empty()) {
        ++cnt;
        rmax[u] = {cnt,cnt};
        return;
    }
    for (int i = 0; i < maxx[u].size(); i++) {
        buildmax(maxx[u][i]);
        rmax[u] = {min(rmax[u].f,rmax[maxx[u][i]].f),max(rmax[u].s,rmax[maxx[u][i]].s)};
    }
}
 
void buildmin(int u) {
    int v = pmin[u][0];
    for (int i = 1; i <= 20; i++) {
        if (v == -1) break;
        pmin[u][i] = pmin[v][i-1];
        v = pmin[u][i];
    }
    if (minn[u].empty()) {
        node[1].push_back(rmax[u].f);
        rmin[u] = {cnt,cnt};
        cnt++;
        return;
    }
    for (int i = 0; i < minn[u].size(); i++) {
        buildmin(minn[u][i]);
        rmin[u] = {min(rmin[u].f,rmin[minn[u][i]].f),max(rmin[u].s,rmin[minn[u][i]].s)};
    }
}

void build(int id, int x, int y) {
    if (x == y) return;
    int mid = (x+y)/2, sum = 0;
    for (int i = 0; i < node[id].size(); i++) {
        if (node[id][i] <= mid) {
            ps[id].push_back(++sum);
            node[id*2].push_back(node[id][i]);
        } else {
            ps[id].push_back(sum);
            node[id*2+1].push_back(node[id][i]);
        }
    }
    build(id*2,x,mid);
    build(id*2+1,mid+1,y);
}
//654213
int query(int id, int x, int y, int l, int r, int pos) {
    /*for (int i = 0; i < ps[id].size(); i++) cout << ps[id][i] << " ";
    cout << endl;
    cout << "e " << x << " " << y << " " << pos << endl;*/
    if (pos == -1) return 0;
    if ((l <= x) && (y <= r)) return pos+1;
    if ((y < l) || (r < x)) return 0;
    int mid = (x+y)/2;
    return query(id*2,x,mid,l,r,ps[id][pos]-1)+query(id*2+1,mid+1,y,l,r,pos-ps[id][pos]);
}

std::vector<signed> check_validity(signed N, std::vector<signed> X, std::vector<signed> Y, std::vector<signed> S, std::vector<signed> E, std::vector<signed> L, std::vector<signed> R) {
    vector<int> ans;
    n = N; m = X.size(); q = S.size();
    for (int i = 0; i < m; i++) {
        edge[X[i]].push_back(Y[i]);
        edge[Y[i]].push_back(X[i]);
    }
    for (int i = 0; i < n+m; i++) for (int j = 0; j <= 20; j++) pmax[i][j] = pmin[i][j] = -1;
    for (int i = 0; i < n; i++) p[i] = id[i] = vmin[i] = i;
    mnsz = n-1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < edge[i].size(); j++) {
            if (edge[i][j] < i) {
                int u = edge[i][j], v = i;
                if (p[dsu(u)] != p[dsu(v)]) {
                    ++mnsz;
                    pmin[id[p[dsu(u)]]][0] = pmin[id[p[dsu(v)]]][0] = mnsz;
                    minn[mnsz].push_back(id[p[dsu(u)]]);
                    minn[mnsz].push_back(id[p[dsu(v)]]);
                    p[dsu(v)] = p[dsu(u)];
                    id[p[dsu(u)]] = mnsz;
                    vmin[mnsz] = i;
                }
            }
        }
    }
    mxsz = n-1;
    for (int i = 0; i < n; i++) p[i] = id[i] = vmax[i] = i;
    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j < edge[i].size(); j++) {
            if (edge[i][j] > i) {
                int u = edge[i][j], v = i;
                if (p[dsu(u)] != p[dsu(v)]) {
                    ++mxsz;
                    pmax[id[p[dsu(u)]]][0] = pmax[id[p[dsu(v)]]][0] = mxsz;
                    maxx[mxsz].push_back(id[p[dsu(u)]]);
                    maxx[mxsz].push_back(id[p[dsu(v)]]);
                    p[dsu(v)] = p[dsu(u)];
                    id[p[dsu(u)]] = mxsz;
                    vmax[mxsz] = i;
                }
            }
        }
    }
    for (int i = 0; i <= mxsz; i++) rmax[i] = {1e9,-1e9};
    for (int i = 0; i <= mnsz; i++) rmin[i] = {1e9,-1e9};
    buildmax(mxsz);
    cnt = 0;
    buildmin(mnsz);
    build(1,1,n);
    /*for (int i = 0; i < node[1].size(); i++) cout << node[1][i] << " ";
    cout << endl;*/
    for (int _ = 0; _ < q; _++) {
        int u = S[_], v = E[_], l = L[_], r = R[_];
        for (int j = 20; j >= 0; j--) if ((pmax[u][j] != -1) && (vmax[pmax[u][j]] >= l)) u = pmax[u][j];
        for (int j = 20; j >= 0; j--) if ((pmin[v][j] != -1) && (vmin[pmin[v][j]] <= r)) v = pmin[v][j];
        /*int sum = 0;
        for (int i = rmin[v].f; i <= rmin[v].s; i++) {
            if ((rmax[u].f <= node[1][i]) && (node[1][i] <= rmax[u].s)) {
                sum++;
            }
        }
        cout << "f ";
        cout << rmin[v].f << " " << rmin[v].s << " " << rmax[u].f << " " << rmax[u].s; // << " " << sum << " " << query(1,1,n,rmax[u].f,rmax[u].s,rmin[v].s)-query(1,1,n,rmax[u].f,rmax[u].s,rmin[v].f-1) << endl;*/
        if (rmin[v].f) ans.push_back(query(1,1,n,rmax[u].f,rmax[u].s,rmin[v].s)-query(1,1,n,rmax[u].f,rmax[u].s,rmin[v].f-1) > 0);
        else ans.push_back(query(1,1,n,rmax[u].f,rmax[u].s,rmin[v].s) > 0);
    }
    return ans;
}

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

werewolf.cpp: In function 'void buildmax(int)':
werewolf.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < maxx[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void buildmin(int)':
werewolf.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < minn[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < node[id].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~
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:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int j = 0; j < edge[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~
werewolf.cpp:110:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for (int j = 0; j < edge[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~

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