oj.uz

Submission #434106

# Submission time Handle Problem Language Result Execution time Memory
434106 2021-06-20T15:03:32 Z vanic Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 36940 KB 
#include "werewolf.h"
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

const int maxn=2e5+5;

struct union_find{
	int kad[maxn];
	int parent[maxn];
	int sz[maxn];
	union_find(){
		for(int i=0; i<maxn; i++){
			parent[i]=i;
			sz[i]=1;
			kad[i]=0;
		}
	}
	int find(int x, int vrij){
		if(kad[x]>vrij || parent[x]==x){
			return x;
		}
		return find(parent[x], vrij);
	}
	void update(int x, int y, int vrij){
		x=find(x, vrij);
		y=find(y, vrij);
		if(sz[x]>sz[y]){
			swap(x, y);
		}
		parent[x]=y;
		kad[x]=vrij;
	}
	bool query(int x, int y, int vrij){
		return find(x, vrij)==find(y, vrij);
	}
};

//int pos1[maxn], pos2[maxn];
vector < int > ms[maxn];
vector < int > s, e, l, r;
vector < int > sol;
int n;
/*
bool cmp1(int a, int b){
	return l[a]>l[b];
}

bool cmp2(int a, int b){
	return r[a]<r[b];
}
*/
union_find U1, U2;

void dodaj1(int x){
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]<x){
			if(!U1.query(x, ms[x][i], x+1)){
				U1.update(x, ms[x][i], x+1);
			}
		}
	}
}

void dodaj2(int x){
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]>x){
			if(!U2.query(x, ms[x][i], n-x)){
				U2.update(x, ms[x][i], n-x);
			}
		}
	}
}
	
vector < int > check_validity(int N, vector < int > x, vector < int > y, vector < int > S, vector < int > E, vector < int > L, vector < int > R){
	s=S;
	e=E;
	l=L;
	r=R;
	n=N;
	int m=x.size();
	for(int i=0; i<m; i++){
		ms[x[i]].push_back(y[i]);
		ms[y[i]].push_back(x[i]);
	}
	int q=s.size();
	for(int i=0; i<n; i++){
		dodaj1(i);
		dodaj2(n-i-1);
	}
	bool p;
	for(int i=0; i<q; i++){
		p=1;
		for(int j=l[i]; j<=r[i]; j++){
			if(U1.query(e[i], j, r[i]+1) && U2.query(s[i], j, n-l[i])){
				sol.push_back(1);
				p=0;
				break;
			}
		}
		if(p){
			sol.push_back(0);
		}
	}
	return sol;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9680 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 7 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 8 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Correct 7 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9680 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 7 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 8 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Correct 7 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 410 ms 10104 KB Output is correct
11 Correct 338 ms 10060 KB Output is correct
12 Correct 89 ms 10060 KB Output is correct
13 Correct 40 ms 10188 KB Output is correct
14 Correct 35 ms 10108 KB Output is correct
15 Correct 2200 ms 10436 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9680 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 7 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 8 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Correct 7 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 410 ms 10104 KB Output is correct
11 Correct 338 ms 10060 KB Output is correct
12 Correct 89 ms 10060 KB Output is correct
13 Correct 40 ms 10188 KB Output is correct
14 Correct 35 ms 10108 KB Output is correct
15 Correct 2200 ms 10436 KB Output is correct
16 Execution timed out 4081 ms 36940 KB Time limit exceeded
17 Halted 0 ms 0 KB -