제출 #878069

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

werewolf

#define SHINLENA2

#ifndef SHINLENA
#include "werewolf.h"
#endif 


#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cstddef>
#include <cassert>
using namespace std;
#define NN 200000
 
 
struct kruskal_reconstruction_tree
{
    vector<int> p, tin, tout, rv;
    int l;
    vector<vector<int>> g;
 
    kruskal_reconstruction_tree(int n, int n0) : p(n), tin(n), tout(n), rv(n), l(n0), g(n)
    {
        iota(p.begin(), p.end(), 0);
    }
 
    int find(int x)
    {
        return x == p[x] ? x : p[x] = find(p[x]);
    }
 
    int unite(int x, int y)
    {
        x = find(x); y = find(y);
        if (x == y) return 0;
        g[p[x] = p[y] = ++l] = {x, y};
        return 1;
    }
 
    int timer = 0;
    void dfs(int u, int p)
    {
        rv[tin[u] = timer++] = u;
        for (auto v : g[u]) if (v != p) dfs(v, u);
        tout[u] = timer - 1;
    }
 
    void tour()
    {
        for (int i = l +1; i--;) if (!tin[i]) dfs(i, i);
    }
};
 

vector<int> t[NN<<3];
 
void add(int v, int l, int r, int p, int k)
{
    t[v].push_back(k);
    if (l == r) return;
    if (p <= (l+r)/2) add(2*v+1, l, (l+r)/2, p, k);
    else add(2*v+2, (l+r)/2+1, r, p, k);
}
 
int qry(int v, int l, int r, int x, int y, int k)
{
    if (r < x || y < l) return 1e9;
    if (x <= l && r <= y)
    {
        auto it = lower_bound(t[v].begin(), t[v].end(), k);
        return it == t[v].end() ? 1e9 : *it;
    }
    return min(qry(2*v+1, l, (l+r)/2, x, y, k), qry(2*v+2, (l+r)/2+1, r, x, y, k));
}
 
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
        vector<int> S, vector<int> E,
        vector<int> L, vector<int> R) {
    int M = X.size();
    kruskal_reconstruction_tree krt1(N+M, N-1);
    kruskal_reconstruction_tree krt2(N+M, N-1);
 
    int Q = S.size();
    vector<int> A(Q);
    vector<vector<int>> g(N);
 
    for (int i = 0; i < M; ++i) g[X[i]].push_back(Y[i]), g[Y[i]].push_back(X[i]);
 
    /* build krt */
    vector<int> rtl(Q), rtr(Q);
    {
        vector<vector<int>> byl(N), byr(N);
        for (int i = 0; i < Q; ++i) byl[L[i]].push_back(i), byr[R[i]].push_back(i);
        for (int i = N; i--;)
        {
            for (auto v : g[i]) if (v >= i) krt1.unite(v, i);
            for (auto j : byl[i]) rtl[j] = krt1.find(S[j]);
        }
        for (int i = 0; i < N; ++i)
        {
            for (auto v : g[i]) if (v <= i) krt2.unite(v, i);
            for (auto j : byr[i]) rtr[j] = krt2.find(E[j]);
        }
    }
 
    krt1.tour();
    krt2.tour();
    
     int LL = krt1.timer - 1;
    /* build merge sort tree */
    {
        vector<pair<int, int>> ins;
        for (int i = 0; i < N; ++i)
             ins.emplace_back(krt2.tin[i], krt1.tin[i]);
             sort(ins.begin(), ins.end());
             for (auto [x, y] : ins) add(0, 0, LL, y, x);
    }
    
    for (int i = 0; i < Q; ++i)
    {
        A[i] = qry(0, 0, LL, krt1.tin[rtl[i]], krt1.tout[rtl[i]], krt2.tin[rtr[i]]) <= krt2.tout[rtr[i]];
    }
 
    return A;
}

#ifdef SHINLENA
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    vector<int>x,y,s,e,l,r;
    for (int u,v,i=0;i<m;++i)cin>>u>>v, x.push_back(u), y.push_back(v);
    
    for (int a,b,c,d,i=0;i<q;++i)
    {
        cin>>a>>b>>c>>d;
        s.push_back(a);
        e.push_back(b);
        l.push_back(c);
        r.push_back(d);
        
    }
    auto A = check_validity(n,x,y,s,e,l,r);
    for (auto x : A) cout << x << endl;
    return 0;
}

#endif

/*

6 6 3
5 1
1 3
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4

*/

컴파일 시 표준 에러 (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:116:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  116 |         for (int i = 0; i < N; ++i)
      |         ^~~
werewolf.cpp:118:14: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  118 |              sort(ins.begin(), ins.end());
      |              ^~~~

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