oj.uz

Submission #991592

# Submission time Handle Problem Language Result Execution time Memory
991592 2024-06-02T14:54:01 Z Lalic Werewolf (IOI18_werewolf) C++17
15 / 100
 422 ms 21076 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3005;

int pai[2][MAXN], peso[2][MAXN];

int find(int tipo, int x){ return (pai[tipo][x]==x ? x : pai[tipo][x]=find(tipo, pai[tipo][x])); }
void join(int tipo, int a, int b){
	a=find(tipo, a);
	b=find(tipo, b);
	if(a==b) return;
	
	if(peso[tipo][a]>peso[tipo][b]) swap(a, b);
	pai[tipo][a]=b;
	peso[tipo][b]=max(peso[tipo][b], peso[tipo][a]+1);
}

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=(int)X.size(), q=(int)L.size();
	vector<int> ans(q);
	for(int i=0;i<q;i++){
		for(int j=0;j<N;j++){
			pai[0][j]=pai[1][j]=j;
			peso[0][j]=peso[1][j]=0;
		}
		
		for(int j=0;j<m;j++){
			if(max(X[j], Y[j])<=R[i]) join(1, X[j], Y[j]);
			if(min(X[j], Y[j])>=L[i]) join(0, X[j], Y[j]);
		}
		
		ans[i]=0;
		for(int j=0;j<N;j++){
			if(find(0, S[i])==find(0, j) && find(1, E[i])==find(1, j)){
				ans[i]=1;
				break;
			}
		}
	}
	
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 296 ms 860 KB Output is correct
11 Correct 257 ms 600 KB Output is correct
12 Correct 270 ms 708 KB Output is correct
13 Correct 271 ms 856 KB Output is correct
14 Correct 234 ms 600 KB Output is correct
15 Correct 422 ms 600 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 87 ms 21076 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 296 ms 860 KB Output is correct
11 Correct 257 ms 600 KB Output is correct
12 Correct 270 ms 708 KB Output is correct
13 Correct 271 ms 856 KB Output is correct
14 Correct 234 ms 600 KB Output is correct
15 Correct 422 ms 600 KB Output is correct
16 Runtime error 87 ms 21076 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -