oj.uz

답안 #991592

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
991592 2024-06-02T14:54:01 Z Lalic 늑대인간 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -