제출 #1155776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155776		weakweakweak	늑대인간 (IOI18_werewolf)	C++20	100 / 100	1191 ms	103776 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using piii = pair<pii, int>;
#define MP make_pair
#define fs first 
#define sc second

struct KruskalTree {
    int n, id = 0;
    vector<int> fa, lid, rid;
    vector<vector<int>> anc, e;
    KruskalTree(int _n, int rt) : n(_n), fa(vector<int>(_n+3, 0)), lid(fa), rid(fa), anc(vector<vector<int>>(21, vector<int>(n+3, rt))), e( vector<vector<int>>(_n+3) ) {};
    int find (int x) {return fa[x] == 0 ? x : fa[x] = find(fa[x]);}
    void merge (int x, int y) {
        x = find(x), y = find(y);
        if (x != y) {
			fa[y] = anc[0][y] = x;
			e[x].push_back(y);
		}
	}
    void baizheng () {
        for (int j = 1; j < 20; j++) for (int i = 1; i <= n; i++) anc[j][i] = anc[j-1][anc[j-1][i]];
    }
	void dfs (int i) {
		lid[i] = ++id;
		for (int j : e[i]) dfs(j);
		rid[i] = id;
	}
};


struct Bit {
	int n;
	vector<int> a;
	Bit (int _n) : a(vector<int>(_n+5,0)), n(_n) {};
	void modify (int i, int val) {for (; i <= n; i+= i&-i) a[i] += val;}
	int askpre (int i) {
		int ret = 0;
		for (; i > 0; i -= i&-i) ret += a[i];
		return ret;
	}
	int query (int l, int r) {return askpre(r) - askpre(l-1);}
};


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();
    vector<int> A(Q,0), id(N+3), hehe(N+3);
    vector<vector<int>> mye(N+3);
	vector<vector<piii>> ins(N+3), del(N+3);
    
	for (int i = 0; i < X.size(); i++) {
		mye[X[i]+1].push_back(Y[i]+1);
		mye[Y[i]+1].push_back(X[i]+1);
	}


	KruskalTree StB (N, N), BtS (N, 1); // 以點權為核心的重構樹
	for (int i = 1; i <= N; i++) {
		for (int j : mye[i]) if (j < i) StB.merge(i, j);
	}
	for (int i = N; i >= 1; i--) {
		for (int j : mye[i]) if (j > i) BtS.merge(i, j);
	}
	StB.baizheng(); BtS.baizheng();
	StB.dfs(N); BtS.dfs(1);

	for (int i = 0; i < Q; i++) {
		S[i]++, E[i]++, L[i]++, R[i]++;
		int rt1 = S[i], rt2 = E[i];
		for (int j = 20; j >= 0; j--) if (BtS.anc[j][rt1] >= L[i]) rt1 = BtS.anc[j][rt1];
		for (int j = 20; j >= 0; j--) if (StB.anc[j][rt2] <= R[i]) rt2 = StB.anc[j][rt2];
		// cout << rt1 << ' ' << rt2 << "   " << BtS.lid[rt1] << ' ' << BtS.rid[rt1] << "   " << StB.lid[rt2] << ' ' << StB.rid[rt2] << '\n';
		if (rt1 < L[i] or rt2 > R[i]) continue;
		ins[BtS.lid[rt1]].push_back(MP(MP(StB.lid[rt2], StB.rid[rt2]), i));
		del[BtS.rid[rt1]].push_back(MP(MP(StB.lid[rt2], StB.rid[rt2]), i));
	}

	// for (int i = 1; i <= N; i++) cout << BtS.lid[i] << ' '; cout << '\n';
	// for (int i = 1; i <= N; i++) cout << StB.lid[i] << ' '; cout << '\n';
	for (int i = 1; i <= N; i++) id[BtS.lid[i]] = StB.lid[i];

	Bit bit(N+2);
	for (int i = 1; i <= N; i++) {
		// cout << id[i] << '\n'; 
		for (auto [p, qid] : ins[i]) A[qid] -= bit.query(p.fs, p.sc);
		bit.modify(id[i], 1); // id[i] 為在 Bts 中壓平後的第 i 項在 StB 的 id
		for (auto [p,qid] : del[i]) {
			A[qid] += bit.query(p.fs, p.sc);
		}
	}
	for (int &x : A) x = (x > 0);

    return A;
}

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