oj.uz

Submission #842369

# Submission time Handle Problem Language Result Execution time Memory
842369 2023-09-02T19:23:21 Z qin Werewolf (IOI18_werewolf) C++17
34 / 100
 581 ms 136700 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, n);
		for(int x = n-1; 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 = 2; 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);
				}
		} 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-1; 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 = 2; 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 127268 KB Output is correct
2 Correct 520 ms 133172 KB Output is correct
3 Correct 491 ms 128616 KB Output is correct
4 Correct 483 ms 126004 KB Output is correct
5 Correct 469 ms 126192 KB Output is correct
6 Correct 488 ms 127344 KB Output is correct
7 Correct 512 ms 123224 KB Output is correct
8 Correct 464 ms 133172 KB Output is correct
9 Correct 432 ms 126220 KB Output is correct
10 Correct 376 ms 124724 KB Output is correct
11 Correct 405 ms 124904 KB Output is correct
12 Correct 469 ms 125040 KB Output is correct
13 Correct 508 ms 136300 KB Output is correct
14 Correct 470 ms 136700 KB Output is correct
15 Correct 458 ms 136448 KB Output is correct
16 Correct 478 ms 136556 KB Output is correct
17 Correct 438 ms 123244 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -