oj.uz

답안 #764460

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764460 2023-06-23T12:23:23 Z ono_de206 늑대인간 (IOI18_werewolf) C++14
0 / 100
 214 ms 127412 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

pair<int, int> operator+(pair<int, int> a, pair<int, int> b) {
	return make_pair(min(a.ff, b.ff), max(a.ss, b.ss));
}

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 Q = S.size();
	vector<int> ret(Q, 0), pos(n);
	vector<vector<int>> g(n);
	for(int i = 0; i < X.size(); i++) {
		g[X[i]].pb(Y[i]);
		g[Y[i]].pb(X[i]);
	}
	int st = 0;
	for(int i = 0; i < n; i++) {
		if(g[i].size() == 1) st = i;
	}
	vector<int> p;
	int x = st, y = g[st][0];
	p.pb(x);
	while(g[y].size() == 2) {
		p.pb(y);
		x ^= g[y][0] ^ g[y][1];
		swap(x, y);
	}
	p.pb(y);

	vector<int> LOG(n + 10);
	for(int i = 2; i < n + 10; i++) {
		LOG[i] = LOG[i / 2] + 1;
	}

	vector<vector<pair<int, int>>> sp(n, vector<pair<int, int>>(20));
	for(int i = 0; i < n; i++) {
		sp[i][0] = {p[i], p[i]};
		pos[p[i]] = i;
	}

	for(int i = 1; i < 20; i++) {
		for(int j = 0; j < n; j++) {
			if(j + (1 << i) > n) break;
			sp[i][j] = sp[i][j - 1] + sp[i + (1 << (i - 1))][j - 1];
		}
	}

	return ret;

	auto get = [&](int l, int r) -> pair<int, int> {
		int id = LOG[r - l + 1];
		return sp[l][id] + sp[r - (1 << id) + 1][id];
	};

	for(int i = 0; i < Q; i++) {
		int s = S[i], e = E[i], l = L[i], r = R[i];
		if(pos[s] > pos[e]) {
			int ll = pos[e], rr = pos[s];
			while(rr - ll > 1) {
				int m = (rr + ll) / 2;
				int mn = get(m, rr).ff;
				if(mn < l) ll = m;
				else rr = m;
			}
			int ans1 = ll + (p[i] < l);
			ll = pos[e], rr = pos[s];
			while(rr - ll > 1) {
				int m = (rr + ll) / 2;
				int mx = get(ll, m).ss;
				if(mx > r) rr = m;
				else ll = m;
			}
			int ans2 = rr - (p[i] > r);
			if(ans2 >= ans1) ret[i] = 1;
		} else {
			int ll = pos[e], rr = pos[s];
			while(rr - ll > 1) {
				int m = (rr + ll) / 2;
				int mn = get(ll, m).ff;
				if(mn < l) rr = m;
				else ll = m;
			}
			int ans1 = rr - (p[i] < l);
			ll = pos[e], rr = pos[s];
			while(rr - ll > 1) {
				int m = (rr + ll) / 2;
				int mx = get(m, rr).ss;
				if(mx > r) ll = m;
				else rr = m;
			}
			int ans2 = ll + (p[i] > r);
			if(ans1 >= ans2) ret[i] = 1;
		}
	}

	return ret;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i = 0; i < X.size(); i++) {
      |                 ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 214 ms 127412 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -