제출 #1049347

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

werewolf

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

using namespace std;

using ll = long long;

struct seg{
	int lb=0, rb=0;
	vector<int> v;
    seg *l=nullptr, *r=nullptr;
	void ext(){
		if(not l and lb!=rb){
			int mb = (lb+rb)/2;
			l = new seg{lb, mb}, r = new seg{mb+1, rb};
		}
	}
	void build(vector<vector<int>> &vv){
		if(lb==rb){
			v = vv[lb];
		}else{
			ext();
			l->build(vv);
			r->build(vv);	
			merge(l->v.begin(), l->v.end(), r->v.begin(), r->v.end(), back_inserter(v));
		}
	}
	ll qry(int lox, int hix, int loy, int hiy){
		if(hix<lb or rb < lox){
			return 0;
		}
		if(lox <= lb and rb  <= hix){
			int ll = lower_bound(v.begin(), v.end(), loy) - v.begin();
			int rr = lower_bound(v.begin(), v.end(), hiy + 1) - v.begin() - 1;
			return max(0, rr - ll + 1);
		}
		ext();
		return l->qry(lox, hix, loy, hiy) + r->qry(lox, hix, loy, hiy);
	}
};

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 Q = S.size();
    int M = X.size();
    std::vector<int> A(Q);

    auto calc = [&](vector<array<int, 3>> e){
        int t = N;
        vector<vector<int>> g(2*N+5);
        vector<int> p(2*N+5, -1);

        auto find = [&](auto find, int u){
            if(p[u]==-1) return u;
            return p[u]=find(find, p[u]); 
        };
        auto join = [&](int u, int v){
            int a = find(find, u), b = find(find, v);
            if(a!=b){
                g[t].push_back(a);
                g[t].push_back(b);
                p[a]=t;
                p[b]=t;
                t++; 
            }
        };
        
        for(auto [cost, u, v]:e){
            join(u, v);
        }
        vector<int> order(N);
        int num = 0; 
        auto dfs = [&](auto dfs, int u) -> void {
            for(int v:g[u]){
                dfs(dfs, v);
            }
            if(u<N)
                order[u]=num++;
        };
        dfs(dfs, t-1);
        return order;
    };

    vector<array<int, 2>> ivx(Q), ivy(Q);

    auto calcinterval = [&](vector<array<int, 3>> e, vector<int> order){
        int t = N;
        vector<int> p(N);
        vector<array<int, 2>> mask(N);
        for(int i=0; i<N; i++) {
            mask[i][0]=mask[i][1]=order[i];
            p[i]=i;
        }

        auto find = [&](auto find, int u){
            if(p[u]==u) return u;
            return p[u]=find(find, p[u]); 
        };
        auto join = [&](int u, int v){
            int a = find(find, u), b = find(find, v);
            if(a!=b){
                p[a] = b;
                mask[b][0] = min(mask[b][0], mask[a][0]);
                mask[b][1] = max(mask[b][1], mask[a][1]);
            }
        };

        vector<array<int, 2>> todo;
        for(int i=0; i<Q; i++){
            todo.push_back({L[i], i});
        }
        sort(todo.begin(), todo.end());
        
        for(auto [cost, u, v]:e){
            while(todo.size() and todo.back()[0] > cost){
                auto [l, id]=todo.back();
                todo.pop_back();
                ivx[id] = mask[find(find, S[id])];
            }
            join(u, v);
        }
        while(todo.size()){
            auto [l, id]=todo.back();
            todo.pop_back();
            ivx[id] = mask[find(find, S[id])];
        }
    };

    auto calcinterval2 = [&](vector<array<int, 3>> e, vector<int> order){
        int t = N;
        vector<int> p(N, -1);
        vector<array<int, 2>> mask(N);
        for(int i=0; i<N; i++) {
            mask[i][0]=mask[i][1]=order[i];
            p[i]=i;
        }

        auto find = [&](auto find, int u){
            if(p[u]==u) return u;
            return p[u]=find(find, p[u]); 
        };
        auto join = [&](int u, int v){
            int a = find(find, u), b = find(find, v);
            if(a!=b){
                p[a] = b;
                mask[b][0] = min(mask[b][0], mask[a][0]);
                mask[b][1] = max(mask[b][1], mask[a][1]);
            }
        };

        vector<array<int, 2>> todo;
        for(int i=0; i<Q; i++){
            todo.push_back({R[i], i});
        }
        sort(todo.begin(), todo.end());
        reverse(todo.begin(), todo.end());
        
        for(auto [cost, u, v]:e){
            while(todo.size() and todo.back()[0] < cost){
                auto [r, id]=todo.back();
                todo.pop_back();
                ivy[id] = mask[find(find, E[id])];
            }
            join(u, v);
        }
        while(todo.size()){
            auto [r, id]=todo.back();
            todo.pop_back();
            ivy[id] = mask[find(find, E[id])];
        }
    };

    vector<array<int, 3>> ex, ey;
    for(int i=0; i<M; i++){
        ex.push_back({min(X[i], Y[i]), X[i], Y[i]});
        ey.push_back({max(X[i], Y[i]), X[i], Y[i]});
    }
    sort(ex.begin(), ex.end());
    reverse(ex.begin(), ex.end());
    sort(ey.begin(), ey.end());

    auto x = calc(ex);
    auto y = calc(ey);

    calcinterval(ex, x);
    calcinterval2(ey, y);


    seg tree = {0, N-1};
    vector<vector<int>> vv(N);
    for(int i=0; i<N; i++){
        vv[x[i]].push_back(y[i]);
    }
    tree.build(vv);

    for(int i=0; i<Q; i++){
        auto [x1, x2] = ivx[i];
        auto [y1, y2] = ivy[i];

        A[i] = tree.qry(x1, x2, y1, y2) > 0;
    }

    /*
    cout<<endl;
    for(int i=0; i<N; i++) cout << i << " " << x[i] << endl;
    cout<<endl;
    for(int i=0; i<N; i++) cout << i << " " << y[i] << endl;
    cout<<endl;
    for(int i=0; i<Q; i++) cout << ivx[i][0] << " " << ivx[i][1] << endl;
    cout<<endl;
    for(int i=0; i<Q; i++) cout << ivy[i][0] << " " << ivy[i][1] << endl;
    */

    return A;
}

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

werewolf.cpp: In lambda function:
werewolf.cpp:88:13: warning: unused variable 't' [-Wunused-variable]
   88 |         int t = N;
      |             ^
werewolf.cpp: In lambda function:
werewolf.cpp:131:13: warning: unused variable 't' [-Wunused-variable]
  131 |         int t = N;
      |             ^

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