oj.uz

답안 #605640

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
605640 2022-07-25T20:44:21 Z AlperenT CEOI16_icc (CEOI16_icc) C++17
90 / 100
 149 ms 504 KB 
#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Comp{
	vector<int> nodes;
};

vector<vector<int>> tree;

vector<bool> vis;

void dfs(int v, vector<int> &vec){
	vis[v] = true;
	vec.push_back(v);

	for(auto e : tree[v]){
		if(!vis[e]) dfs(e, vec);
	}
}

bool cmp(Comp &a, Comp &b){
	return a.nodes.size() > b.nodes.size();
}

void run(int n){
	tree.assign(n + 1, {});

	int mx = 0;

	for(int it = 0; it <= n - 1; it++){
		int s, t;

		vector<Comp> comps;

		vis.assign(n + 1, false);

		for(int v = 1; v <= n; v++){
			if(!vis[v]){
				Comp tmp;

				comps.push_back(tmp);
				dfs(v, comps.back().nodes);
			}
		}

		sort(comps.begin(), comps.end(), cmp);

		vector<int> a, b, c;

		for(int k = __lg(comps.size()); k >= 0; k--){
			a.clear(), b.clear();

			for(int i = 0; i < comps.size(); i++){
				if(i & (1 << k)) for(auto v : comps[i].nodes) a.push_back(v);
				else for(auto v : comps[i].nodes) b.push_back(v);
			}

			if(query(a.size(), b.size(), a.data(), b.data())) break;
		}

		shuffle(a.begin(), a.end(), rng);
		shuffle(b.begin(), b.end(), rng);

		int l = -1, r = a.size() - 1, m;

		while(r - l > 1){
			m = l + (r - l) / 2;

			c.clear();

			for(int i = 0; i <= m; i++) c.push_back(a[i]);

			if(query(c.size(), b.size(), c.data(), b.data())) r = m;
			else l = m;
		}

		s = a[r];

		l = -1, r = b.size() - 1;

		while(r - l > 1){
			m = l + (r - l) / 2;

			c.clear();

			for(int i = 0; i <= m; i++) c.push_back(b[i]);

			if(query(c.size(), a.size(), c.data(), a.data())) r = m;
			else l = m;
		}

		t = b[r];

		setRoad(s, t);

		tree[s].push_back(t);
		tree[t].push_back(s);
	}
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:57:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Comp>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |    for(int i = 0; i < comps.size(); i++){
      |                   ~~^~~~~~~~~~~~~~
icc.cpp:32:6: warning: unused variable 'mx' [-Wunused-variable]
   32 |  int mx = 0;
      |      ^~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 468 KB Ok! 105 queries used.
2 Correct 9 ms 504 KB Ok! 107 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 468 KB Ok! 581 queries used.
2 Correct 40 ms 468 KB Ok! 695 queries used.
3 Correct 36 ms 480 KB Ok! 680 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 488 KB Ok! 1532 queries used.
2 Correct 124 ms 488 KB Ok! 1693 queries used.
3 Correct 125 ms 492 KB Ok! 1649 queries used.
4 Correct 115 ms 492 KB Ok! 1584 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 492 KB Ok! 1641 queries used.
2 Correct 117 ms 488 KB Ok! 1631 queries used.
3 Correct 128 ms 496 KB Ok! 1666 queries used.
4 Correct 127 ms 488 KB Ok! 1577 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 492 KB Ok! 1657 queries used.
2 Correct 122 ms 468 KB Ok! 1672 queries used.
3 Correct 132 ms 488 KB Ok! 1664 queries used.
4 Correct 145 ms 488 KB Ok! 1666 queries used.
5 Correct 131 ms 492 KB Ok! 1572 queries used.
6 Correct 112 ms 468 KB Ok! 1591 queries used.

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 149 ms 488 KB Too many queries! 1665 out of 1625
2 Halted 0 ms 0 KB -