oj.uz

Submission #991586

# Submission time Handle Problem Language Result Execution time Memory
991586 2024-06-02T14:36:38 Z Lalic Werewolf (IOI18_werewolf) C++17
0 / 100
 97 ms 26116 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) {
	vector<int> ans((int)L.size());
	for(int i=0;i<(int)L.size();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<(int)X.size();j++){
			if(max(X[j], Y[j])<=R[i]) join(0, X[j], Y[j]);
			if(min(X[j], Y[j])>=L[i]) join(1, 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -