제출 #392499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
392499		Jarif_Rahman	늑대인간 (IOI18_werewolf)	C++17	0 / 100	4014 ms	74180 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, m, q;

struct reachability_tree{
    int n;
    vector<int> p;
    vector<int> w;
    vector<vector<int>> v;
    reachability_tree(int _n){
        n = _n;
        p.resize(n);
        w.resize(n);
        v.resize(n);
        for(int i = 0; i < n; i++) p[i] = i;
    }
    int get(int x){
        if(p[x] != x) p[x] = get(p[x]);
        return p[x];
    }
    void unite(int a, int b, int vl){
        a = get(a), b = get(b);
        p[a] = n, p[b] = n;
        p.pb(n);
        v.pb({});
        v[n].pb(a);
        if(a != b) v[n].pb(b);
        w.pb(vl);
        n++;
    }
};

vector<int> szl, szr;
vector<int> sl, sr;
void dfs(int nd, vector<int> *sz, vector<int> *s, vector<vector<int>> *v){
    s->pb(nd);
    for(int x: (*v)[nd]){
        dfs(x, sz, s, v);
        (*sz)[nd]+=(*sz)[x];
    }
}

vector<int> check_validity(int n, vector<int> U, vector<int> V, vector<int> ss, vector<int> ee, vector<int> lv, vector<int> rv){
    ::n = n, ::m = U.size(), ::q = ss.size();
    vector<pair<int, int>> edges;
    for(int i = 0; i < m; i++) edges.pb({U[i], V[i]});
    vector<array<int, 7>> query;
    for(int i = 0; i < q; i++) query.pb({ss[i], ee[i], lv[i], rv[i], -1, -1, i});
    reachability_tree rtl(n), rtr(n);
    sort(edges.begin(), edges.end(), [&](pair<int, int> a, pair<int, int> b){return max(a.f, a.sc) < max(b.f, b.sc);});
    sort(query.begin(), query.end(), [&](array<int, 7> a, array<int, 7> b){return a[3] < b[3];});
    int cur = 0;
    for(int i = 0; i < m; i++){
        auto [a, b] = edges[i];
        int wi = max(a, b);
        rtl.unite(a, b, wi);
        if(i == m-1 || wi != max(get<0>(edges[i+1]), get<1>(edges[i+1]))){
            while(cur < query.size() && query[cur][3] <= wi) query[cur][4] = rtl.get(query[cur][1]), cur++;
        }
    }
    sort(edges.begin(), edges.end(), [&](pair<int, int> a, pair<int, int> b){return min(a.f, a.sc) > min(b.f, b.sc);});
    sort(query.begin(), query.end(), [&](array<int, 7> a, array<int, 7> b){return a[2] > b[2];});
    cur = 0;
    for(int i = 0; i < m; i++){
        auto [a, b] = edges[i];
        int wi = min(a, b);
        rtr.unite(a, b, wi);
        if(i == m-1 || wi != min(get<0>(edges[i+1]), get<1>(edges[i+1]))){
            while(cur < query.size() && query[cur][2] >= wi) query[cur][5] = rtr.get(query[cur][0]), cur++;
        }
    }
    szl.resize(rtl.n, 1);
    szr.resize(rtr.n, 1);
    dfs(rtl.get(0), &szl, &sl, &rtl.v);
    dfs(rtr.get(0), &szr, &sr, &rtr.v);
    vector<int> ans(q, 0);
    vector<int> sttl(rtl.n), sttr(rtr.n);
    for(int i = 0; i < rtl.n; i++) sttl[sl[i]] = i;
    for(int i = 0; i < rtr.n; i++) sttr[sr[i]] = i;
    for(array<int, 7> qq: query){
        if(qq[0] < qq[2] || qq[1] > qq[4]) continue;
        for(int i = sttl[qq[4]]; i < sttl[qq[4]] + szl[qq[4]]; i++) for(int j = sttr[qq[5]]; j < sttr[qq[5]] + szr[qq[5]]; j++) if(sl[i] == sr[j] && sl[i] < n) ans[qq[6]] = 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:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 7> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             while(cur < query.size() && query[cur][3] <= wi) query[cur][4] = rtl.get(query[cur][1]), cur++;
      |                   ~~~~^~~~~~~~~~~~~~
werewolf.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 7> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             while(cur < query.size() && query[cur][2] >= wi) query[cur][5] = rtr.get(query[cur][0]), cur++;
      |                   ~~~~^~~~~~~~~~~~~~

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