Submission #595115

#	Time	Username	Problem	Language	Result	Execution time	Memory
595115		FatihSolak	Werewolf (IOI18_werewolf)	C++17	100 / 100	3014 ms	227528 KiB

werewolf

#include "werewolf.h"
#define N 200005
#include <bits/stdc++.h>
using namespace std;
struct change{
	int version;
	int to;
};
vector<change> changes[N];
vector<int> adj[N];
vector<int> graph_times[N];
unordered_map<int,int> mp[N];
vector<int> v[N];
int group[N];
vector<int> queries[N];
void merge(int a,int b,int time){
	a = group[a];
	b = group[b];
	if(a == b)
		return;
	if(v[a].size() > v[b].size()){
		swap(a,b);
	}
	graph_times[b].push_back(time);
	for(auto u:v[a]){
		changes[u].push_back({graph_times[b].size(),b});
		group[u] = b;
		v[b].push_back(u);
	}
}
void merge2(int a,int b){
	a = group[a];
	b = group[b];
	if(a == b)
		return;
	if(v[a].size() > v[b].size()){
		swap(a,b);
	}
	for(auto u:v[a]){
		group[u] = b;
		v[b].push_back(u);
		for(auto c:changes[u]){
			if(mp[c.to][b] == 0 || mp[c.to][b] > c.version){
				mp[c.to][b] = c.version;
			}
		}
	}
}
bool ck(int x,int time,int target){
	int group = -1;
	for(auto u:changes[x]){
		if(graph_times[u.to][u.version-1] <= time){
			group = u.to;
		}
	}
	int version = upper_bound(graph_times[group].begin(),graph_times[group].end(),time) - graph_times[group].begin();
	if(mp[group][target] && mp[group][target] <= version){
		return 1;
	}
	return 0;
}
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 = x.size();
	int q = s.size();
	for(int i = 0;i<m;i++){
		adj[x[i]].push_back(y[i]);
		adj[y[i]].push_back(x[i]);
	}
	for(int i = 0;i<n;i++){
		v[i] = {i};
		group[i] = i;
		changes[i].push_back({1,i});
		graph_times[i].push_back(-1);
	}
	vector<int> ans(q);
	for (int i = 0; i < q; ++i) {
		queries[l[i]].push_back(i);
	}
	for(int i = 0;i<n;i++){
		for(auto u:adj[i]){
			if(u < i){
				merge(u,i,i);
			}
		}
	}
	for(int i = 0;i<n;i++){
		v[i] = {i};
		group[i] = i;
		for(auto u:changes[i]){
			if(mp[u.to][i] == 0 || mp[u.to][i] > u.version){
				mp[u.to][i] = u.version;
			}
		}
	}
	for(int i = n-1;i>=0;i--){
		for(auto u:adj[i]){
			if(i < u){
				merge2(u,i);
			}
		}
		for(auto u:queries[i]){
			ans[u] = ck(e[u],r[u],group[s[u]]);
		}
	}
	return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void merge(int, int, int)':
werewolf.cpp:26:44: warning: narrowing conversion of 'graph_times[b].std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   26 |   changes[u].push_back({graph_times[b].size(),b});
      |                         ~~~~~~~~~~~~~~~~~~~^~

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