oj.uz

답안 #842374

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
842374 2023-09-02T19:30:53 Z qin 늑대인간 (IOI18_werewolf) C++17
100 / 100
 596 ms 156788 KB 
#ifdef LOCAL
#else
#include <werewolf.h>
#endif
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pli;
typedef double db;
typedef long double ldb;
struct st_query{
		int s, e, l, r, i;
		st_query(){}
		st_query(int S, int E, int L, int R) : s(S), e(E), l(L), r(R) {}
};
struct DSU{
		int c;
		vector<int> rep;
		void init(int n, int N){ c = N, rep = vector<int>(), rep.resize(n+1); for(int i = 1; i <= n; ++i) rep[i] = i; }
		int Find(int x){
				int b;
				if(x != rep[x]) b = x, x = Find(rep[x]), rep[b] = x;
				return x; 
		} void add_edge(int u, int v, vector<vector<int>> &g){
				u = Find(u), v = Find(v);
				if(u == v) return;
				g[++c].emplace_back(u), g[c].emplace_back(v);
				rep[u] = c, rep[v] = c;
		}
} DSU;
void dfs(int x, int &c, vector<vector<int>> &g, vector<pii> &preorder){
		++c, preorder[x].fi = c;
		for(int u : g[x]) dfs(u, c, g, preorder);
		preorder[x].se = c;
} struct st_event{
		int type; // 0 - poczatek -> query / 1 - punkt -> add / 2 - koniec -> query
		int l, r, i;
		st_event(){}
		st_event(int L) : type(1), l(L) {}
		st_event(int T, int L, int R, int I) : type(T), l(L), r(R), i(I) {}
		bool operator <(const st_event &x) { return type < x.type; }
}; int base = 1;
struct seg{
		vector<int> t;
		void init(int n){
				while(base < n) base <<= 1;
				t.resize(base<<1);
		} void add(int x){for(x += base-1; x; x >>= 1) ++t[x];}
		int query(int i, int pocz, int kon, int x, int y){
				if(x <= pocz && kon <= y) return t[i];
				int sr = (pocz+kon)>>1, wynik = 0;
				if(x <= sr) wynik += query(i<<1, pocz, sr, x, y);
				if(sr < y) wynik += query(i<<1|1, sr+1, kon, x, y);
				return wynik;
		}
} seg;
#ifdef LOCAL
int main(){
		int n, m, q, a, b; scanf("%d%d%d", &n, &m, &q);
		vector<vector<int>> g_greater(n+1), g_smaller(n+1);
		vector<st_query> v_query(q);
		vector<vector<pii>> starts(n+1), ends(n+1);
		for(int i = 0; i < m; ++i){
				scanf("%d%d", &a, &b); ++a, ++b;
				if(a > b) swap(a, b);
				g_greater[a].emplace_back(b), g_smaller[b].emplace_back(a);
		} for(int i = 0; i < q; ++i){
				scanf("%d%d%d%d", &v_query[i].s, &v_query[i].e, &v_query[i].l, &v_query[i].r);
				++v_query[i].s, ++v_query[i].e, ++v_query[i].l, ++v_query[i].r, v_query[i].i = i;
				starts[v_query[i].l].emplace_back(v_query[i].s, i), ends[v_query[i].r].emplace_back(v_query[i].e, i);
		} vector<vector<int>> gL(n+m+1), gR(n+m+1);
		vector<int> query_nodes_L(q), query_nodes_R(q);
		vector<pii> preorderL(n+m+1), preorderR(n+m+1);
		//tworzenie pierwszego drzewa (dla L)
		DSU.init(n+m+1, n);
		for(int x = n; x; --x){
				for(int u : g_greater[x]) DSU.add_edge(x, u, gL);
				for(pii s : starts[x]) query_nodes_L[s.se] = DSU.Find(s.fi);
		} int cnt = 0; dfs(DSU.c, cnt, gL, preorderL);
		//tworzenie drugiego drzewa (dla R)
		DSU.init(n+m+1, n);
		for(int x = 1; x <= n; ++x){
				for(int u : g_smaller[x]) DSU.add_edge(x, u, gR);
				for(pii s : ends[x]) query_nodes_R[s.se] = DSU.Find(s.fi);
		} cnt = 0; dfs(DSU.c, cnt, gR, preorderR);
		//tworzenie zamiatania
		seg.init(n+m+2);
		vector<vector<st_event>> t(n+m+1);
		for(int i = 0; i < q; ++i)
				t[preorderL[query_nodes_L[i]].fi].emplace_back(0, preorderR[query_nodes_R[i]].fi, preorderR[query_nodes_R[i]].se, i),
				t[preorderL[query_nodes_L[i]].se].emplace_back(2, preorderR[query_nodes_R[i]].fi, preorderR[query_nodes_R[i]].se, i);
		for(int i = 1; i <= n; ++i) t[preorderL[i].fi].emplace_back(preorderR[i].fi);
		vector<int> wynik(q);
		for(int i = 1; i <= n+m; ++i){
				sort(t[i].begin(), t[i].end());
				for(st_event u : t[i]){
						if(!u.type) wynik[u.i] = seg.query(1, 1, base, u.l, u.r);
						else if(u.type == 2) wynik[u.i] = min(1, seg.query(1, 1, base, u.l, u.r) - wynik[u.i]);
						else seg.add(u.l);
				}
		} for(int i : wynik) printf("%d\n", i);
		return 0;
}
#else
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 = ssize(X), q = ssize(S), a, b;
		vector<vector<int>> g_greater(n+1), g_smaller(n+1);
		vector<st_query> v_query(q);
		vector<vector<pii>> starts(n+1), ends(n+1);
		for(int i = 0; i < m; ++i){
				a = X[i], b = Y[i], ++a, ++b;
				if(a > b) swap(a, b);
				g_greater[a].emplace_back(b), g_smaller[b].emplace_back(a);
		} for(int i = 0; i < q; ++i){
				v_query[i].s = S[i], v_query[i].e = E[i], v_query[i].l = L[i], v_query[i].r = R[i];
				++v_query[i].s, ++v_query[i].e, ++v_query[i].l, ++v_query[i].r, v_query[i].i = i;
				starts[v_query[i].l].emplace_back(v_query[i].s, i), ends[v_query[i].r].emplace_back(v_query[i].e, i);
		} vector<vector<int>> gL(n+m+1), gR(n+m+1);
		vector<int> query_nodes_L(q), query_nodes_R(q);
		vector<pii> preorderL(n+m+1), preorderR(n+m+1);
		//tworzenie pierwszego drzewa (dla L)
		DSU.init(n+m, n);
		for(int x = n; x; --x){
				for(int u : g_greater[x]) DSU.add_edge(x, u, gL);
				for(pii s : starts[x]) query_nodes_L[s.se] = DSU.Find(s.fi);
		} int cnt = 0; dfs(DSU.c, cnt, gL, preorderL);
		//tworzenie drugiego drzewa (dla R)
		DSU.init(n+m, n);
		for(int x = 1; x <= n; ++x){
				for(int u : g_smaller[x]) DSU.add_edge(x, u, gR);
				for(pii s : ends[x]) query_nodes_R[s.se] = DSU.Find(s.fi);
		} cnt = 0; dfs(DSU.c, cnt, gR, preorderR);
		//tworzenie zamiatania
		seg.init(n+m+1);
		vector<vector<st_event>> t(n+m+1);
		for(int i = 0; i < q; ++i)
				t[preorderL[query_nodes_L[i]].fi].emplace_back(0, preorderR[query_nodes_R[i]].fi, preorderR[query_nodes_R[i]].se, i),
				t[preorderL[query_nodes_L[i]].se].emplace_back(2, preorderR[query_nodes_R[i]].fi, preorderR[query_nodes_R[i]].se, i);
		for(int i = 1; i <= n; ++i) t[preorderL[i].fi].emplace_back(preorderR[i].fi);
		vector<int> wynik(q);
		for(int i = 1; i <= n+m; ++i){
				sort(t[i].begin(), t[i].end());
				for(st_event u : t[i]){
						if(!u.type) wynik[u.i] = seg.query(1, 1, base, u.l, u.r);
						else if(u.type == 2) wynik[u.i] = min(1, seg.query(1, 1, base, u.l, u.r) - wynik[u.i]);
						else seg.add(u.l);
				}
		}
		return wynik;
} 
#endif

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 440 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 440 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 7 ms 2396 KB Output is correct
11 Correct 5 ms 2140 KB Output is correct
12 Correct 5 ms 2140 KB Output is correct
13 Correct 6 ms 2340 KB Output is correct
14 Correct 5 ms 2492 KB Output is correct
15 Correct 6 ms 2652 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 531 ms 118912 KB Output is correct
2 Correct 477 ms 124724 KB Output is correct
3 Correct 460 ms 119860 KB Output is correct
4 Correct 515 ms 118000 KB Output is correct
5 Correct 481 ms 117816 KB Output is correct
6 Correct 508 ms 118732 KB Output is correct
7 Correct 460 ms 114800 KB Output is correct
8 Correct 528 ms 124668 KB Output is correct
9 Correct 510 ms 117816 KB Output is correct
10 Correct 392 ms 116332 KB Output is correct
11 Correct 425 ms 116472 KB Output is correct
12 Correct 479 ms 116688 KB Output is correct
13 Correct 525 ms 128216 KB Output is correct
14 Correct 558 ms 127876 KB Output is correct
15 Correct 507 ms 128052 KB Output is correct
16 Correct 521 ms 128068 KB Output is correct
17 Correct 466 ms 114996 KB Output is correct

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 440 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 7 ms 2396 KB Output is correct
11 Correct 5 ms 2140 KB Output is correct
12 Correct 5 ms 2140 KB Output is correct
13 Correct 6 ms 2340 KB Output is correct
14 Correct 5 ms 2492 KB Output is correct
15 Correct 6 ms 2652 KB Output is correct
16 Correct 531 ms 118912 KB Output is correct
17 Correct 477 ms 124724 KB Output is correct
18 Correct 460 ms 119860 KB Output is correct
19 Correct 515 ms 118000 KB Output is correct
20 Correct 481 ms 117816 KB Output is correct
21 Correct 508 ms 118732 KB Output is correct
22 Correct 460 ms 114800 KB Output is correct
23 Correct 528 ms 124668 KB Output is correct
24 Correct 510 ms 117816 KB Output is correct
25 Correct 392 ms 116332 KB Output is correct
26 Correct 425 ms 116472 KB Output is correct
27 Correct 479 ms 116688 KB Output is correct
28 Correct 525 ms 128216 KB Output is correct
29 Correct 558 ms 127876 KB Output is correct
30 Correct 507 ms 128052 KB Output is correct
31 Correct 521 ms 128068 KB Output is correct
32 Correct 466 ms 114996 KB Output is correct
33 Correct 550 ms 128564 KB Output is correct
34 Correct 241 ms 88408 KB Output is correct
35 Correct 596 ms 134580 KB Output is correct
36 Correct 563 ms 128612 KB Output is correct
37 Correct 569 ms 132580 KB Output is correct
38 Correct 586 ms 130292 KB Output is correct
39 Correct 593 ms 141420 KB Output is correct
40 Correct 576 ms 156788 KB Output is correct
41 Correct 481 ms 130028 KB Output is correct
42 Correct 419 ms 125840 KB Output is correct
43 Correct 572 ms 146860 KB Output is correct
44 Correct 508 ms 131976 KB Output is correct
45 Correct 461 ms 139460 KB Output is correct
46 Correct 434 ms 139056 KB Output is correct
47 Correct 473 ms 137092 KB Output is correct
48 Correct 484 ms 136460 KB Output is correct
49 Correct 519 ms 137152 KB Output is correct
50 Correct 509 ms 136524 KB Output is correct
51 Correct 512 ms 156248 KB Output is correct
52 Correct 527 ms 155976 KB Output is correct