oj.uz

Submission #595113

# Submission time Handle Problem Language Result Execution time Memory
595113 2022-07-13T11:20:45 Z FatihSolak Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 239316 KB 
#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];
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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33108 KB Output is correct
2 Correct 23 ms 33184 KB Output is correct
3 Correct 20 ms 33192 KB Output is correct
4 Correct 22 ms 33192 KB Output is correct
5 Correct 21 ms 33236 KB Output is correct
6 Correct 20 ms 33152 KB Output is correct
7 Correct 20 ms 33208 KB Output is correct
8 Correct 21 ms 33236 KB Output is correct
9 Correct 21 ms 33184 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33108 KB Output is correct
2 Correct 23 ms 33184 KB Output is correct
3 Correct 20 ms 33192 KB Output is correct
4 Correct 22 ms 33192 KB Output is correct
5 Correct 21 ms 33236 KB Output is correct
6 Correct 20 ms 33152 KB Output is correct
7 Correct 20 ms 33208 KB Output is correct
8 Correct 21 ms 33236 KB Output is correct
9 Correct 21 ms 33184 KB Output is correct
10 Correct 30 ms 34660 KB Output is correct
11 Correct 28 ms 34736 KB Output is correct
12 Correct 34 ms 35508 KB Output is correct
13 Correct 27 ms 34500 KB Output is correct
14 Correct 27 ms 34736 KB Output is correct
15 Correct 29 ms 34856 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4064 ms 239316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33108 KB Output is correct
2 Correct 23 ms 33184 KB Output is correct
3 Correct 20 ms 33192 KB Output is correct
4 Correct 22 ms 33192 KB Output is correct
5 Correct 21 ms 33236 KB Output is correct
6 Correct 20 ms 33152 KB Output is correct
7 Correct 20 ms 33208 KB Output is correct
8 Correct 21 ms 33236 KB Output is correct
9 Correct 21 ms 33184 KB Output is correct
10 Correct 30 ms 34660 KB Output is correct
11 Correct 28 ms 34736 KB Output is correct
12 Correct 34 ms 35508 KB Output is correct
13 Correct 27 ms 34500 KB Output is correct
14 Correct 27 ms 34736 KB Output is correct
15 Correct 29 ms 34856 KB Output is correct
16 Execution timed out 4064 ms 239316 KB Time limit exceeded
17 Halted 0 ms 0 KB -