oj.uz

답안 #1112875

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1112875 2024-11-15T06:54:30 Z Jawad_Akbar_JJ CEOI16_icc (CEOI16_icc) C++17
100 / 100
 94 ms 764 KB 
#include <iostream>
#include <vector>
#include <set>
#include "icc.h"

using namespace std;
set<int> rt;
vector<int> Vec[105];
int Root[105], seen[105][105];

vector<int> get(vector<int> a){
	vector<int> ans;
	for (int i : a)
		for (int j : Vec[i])
			ans.push_back(j);
	return ans;
}

bool Query(vector<int> a,vector<int> b){
	int n1 = a.size(), n2 = b.size();
	return query(n1, n2, &a[0], &b[0]);
}

void solve2(vector<int> lft, vector<int> rgt){
	lft = get(lft);
	int l = 0, r = lft.size();
	while (l + 1 < r){
		int m = (l + r) / 2;
		vector<int> vec2;
		
		for (int i = l;i < m;i++)
			vec2.push_back(lft[i]);
		
		if (Query(vec2, get(rgt)))
			r = m;
		else
			l = m;
	}

	vector<int> v;
	for (int i : rgt)
		if (!seen[Root[lft[l]]][i])
			v.push_back(i);
	rgt = get(v);

	int l2 = 0, r2 = rgt.size();

	while (l2 + 1 < r2){
		int m2 = (l2 + r2) / 2;
		vector<int> vec2;
		for (int i=l2;i<m2;i++)
			vec2.push_back(rgt[i]);

		if (Query({lft[l]}, vec2))
			r2 = m2;
		else
			l2 = m2;
	}

	int A = lft[l], B = rgt[l2];

	setRoad(A, B);
	A = Root[A], B = Root[B];

	for (int i : Vec[B])
		Root[i] = A, Vec[A].push_back(i);
	rt.erase(B);
}

void solve(int n){
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			seen[i][j] = 0;

	vector<int> V;
	for (int i : rt)
		V.push_back(i);

	for (int p=(1<<20);p >= 1;p /= 2){
		if (p >= V.size())
			continue;
		vector<int> lft, rgt;
		for (int j=0, l = 0;j<V.size();j++){
			if (j % p == 0)
				l = 1 - l;
			if (l)
				lft.push_back(V[j]);
			else
				rgt.push_back(V[j]);
		}

		if (Query(get(lft), get(rgt))){
			solve2(lft, rgt);
			return ;
		}
		for (int i : lft)
			for (int j : rgt)
				seen[i][j] = seen[j][i] = 1;
	}
}

void run(int n){
	for (int i=1;i<=n;i++){
		Root[i] = i;
		Vec[i].push_back(i);
		rt.insert(i);
	}
	for (int i=1;i<n;i++)
		solve(n);
}

Compilation message

icc.cpp: In function 'void solve(int)':
icc.cpp:80:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   if (p >= V.size())
      |       ~~^~~~~~~~~~~
icc.cpp:83:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for (int j=0, l = 0;j<V.size();j++){
      |                       ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 592 KB Ok! 101 queries used.
2 Correct 6 ms 652 KB Ok! 100 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 760 KB Ok! 529 queries used.
2 Correct 28 ms 660 KB Ok! 569 queries used.
3 Correct 25 ms 592 KB Ok! 587 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 592 KB Ok! 1356 queries used.
2 Correct 90 ms 700 KB Ok! 1411 queries used.
3 Correct 84 ms 692 KB Ok! 1384 queries used.
4 Correct 70 ms 692 KB Ok! 1353 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 764 KB Ok! 1409 queries used.
2 Correct 74 ms 700 KB Ok! 1424 queries used.
3 Correct 81 ms 696 KB Ok! 1520 queries used.
4 Correct 66 ms 688 KB Ok! 1287 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 684 KB Ok! 1511 queries used.
2 Correct 83 ms 592 KB Ok! 1499 queries used.
3 Correct 74 ms 592 KB Ok! 1480 queries used.
4 Correct 77 ms 592 KB Ok! 1499 queries used.
5 Correct 92 ms 688 KB Ok! 1370 queries used.
6 Correct 70 ms 688 KB Ok! 1339 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 692 KB Ok! 1508 queries used.
2 Correct 94 ms 692 KB Ok! 1513 queries used.