Submission #989761

#	Time	Username	Problem	Language	Result	Execution time	Memory
989761		OAleksa	Werewolf (IOI18_werewolf)	C++14	15 / 100	4043 ms	47640 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 2e5 + 69;
/*
g++ werewolf.cpp werewolf.h grader.cpp
./a.out
*/
int p[N], sz[N];
vector<pair<int, int>> t[N];
vector<pair<int, int>> qs[N];
vector<int> g[N];
int root(int v) {
	if (p[v] == v)
		return v;
	return p[v] = root(p[v]);
}
vector<int> check_validity(int n, vector<int> u, vector<int> v, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
  int q = s.size();
  int m = u.size();
  vector<int> ans(q);
  vector<tuple<int, int, int>> edges;
  for (int i = 0;i < m;i++) {
  	++u[i], ++v[i];
  	g[u[i]].push_back(v[i]);
  	g[v[i]].push_back(u[i]);
  }
  for (int i = 0;i < q;i++) {
  	l[i]++, r[i]++;
  	s[i]++, e[i]++;
  }
  for (int i = 1;i <= n;i++) {
  	p[i] = i;
  	sz[i] = 1;
  }
  for (int i = 0;i < q;i++) 
  	qs[l[i]].push_back({r[i], i});
  for (int i = 0;i < m;i++) {
  	int a = u[i], b = v[i];
  	int c = min(a, b);
  	edges.push_back({c, a, b});
  }
  sort(edges.begin(), edges.end());
  int ptr = m - 1;
  for (int i = n;i >= 1;i--) {
  	while (ptr >= 0 && get<0>(edges[ptr]) >= i) {
  		int a = get<1>(edges[ptr]), b = get<2>(edges[ptr]);
  		ptr--;
  		int x = root(a), y = root(b);
  		if (x != y) {
  			if (sz[x] < sz[y])
  				swap(x, y);
  			sz[x] += sz[y];
  			p[y] = x;
  		}
  	}
  	for (auto j : qs[i]) {
  		int r = j.f, ind = j.s;
  		queue<int> q;
  		vector<int> vis(n + 1);
  		for (int k = 1;k <= n;k++) {
  			if (root(k) == root(s[ind]) && k >= i && k <= r) {
  				q.push(k);
  			}
  		}
  		while (!q.empty()) {
  			auto v = q.front();
  			q.pop();
  			vis[v] = 1;
  			for (auto u : g[v]) {
  				if (vis[u] || u > r)
  					continue;
  				vis[u] = 1;
  				q.push(u);
  			}
  		}
  		ans[ind] = vis[e[ind]];
  	}
  }
  return ans;
}
/*
6 6 3
5 1
1 2
2 5
1 3
3 4
0 3
4 2 1 2
4 2 2 2
5 4 3 4
*/

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