oj.uz

Submission #203467

# Submission time Handle Problem Language Result Execution time Memory
203467 2020-02-20T20:08:48 Z kostia244 ICC (CEOI16_icc) C++17
100 / 100
 187 ms 632 KB 
#define _GLIBCXX_DEBUG
#ifndef kostia
#include"icc.h"
#endif
#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<int, int>;
using vpi = vector<pi>;
#ifdef kostia
vpi local_roads;
int local_cur = 0, local_n;
int query(int sa, int sb, int a[], int b[]) {
	cout << sa << " " << sb << " :: ";
	for(int i = 0; i < sa; i++) cout << a[i] << " "; cout << " - ";
	for(int i = 0; i < sb; i++) cout << b[i] << " "; cout << "\n";
	cout << endl;
	for(int i = 0; i < sa; i++) {
		for(int j = 0; j < sb; j++) {
			for(auto k : local_roads) {
				if(a[i]==k.first && b[j]==k.second)
					return 1;
				if(a[i]==k.second && b[j]==k.first)
					return 1;
			}
		}
	}
	return 0;
}
void setRoad(int a, int b) {
	if(pi{a, b}!=local_roads.back()&&pi{b, a}!=local_roads.back()) {
		cout << a << " " << b << "\n";
		cout << "BAD";
		exit(0);
	}
	cout << "road " << local_roads.back().first << " " << local_roads.back().second << " guessed.\n";
	if(++local_cur==local_n) exit(0);
	cin >> a >> b;
	local_roads.pb({a, b});
}
#endif
const int maxn = 1e2 + 21;
struct dsu {
	vi r, p, c;
	void init(int n) {
		r.resize(n+1);
		p.resize(n+1);
		c.resize(n+1);
		for(int i = 1; i <= n; i++) {
			r[i] = 1, p[i] = i;
		}
	}
	int par(int i) {
		if(i==p[i]) return i;
		return p[i] = par(p[i]);
	}
	void unite(int i, int j) {
		i = par(i), j = par(j);
		if(i==j) return;
		if(r[i] < r[j]) swap(i, j);
		p[j] = i;
		r[i] += r[i] == r[j];
	}
	bool con(int i, int j) {
		return par(i) == par(j);
	}
	int col(int i) {
		return c[par(i)];
	}
	void paint(int i, int j) {
		c[par(i)] = j;
	}
};
int n;
int a[maxn], b[maxn];
dsu d;
int q(vi x, vi y, int v = 1000) {
	if(x.empty()||y.empty()) return 0;
	for(int i = 0; i < min(v, (int)x.size()); i++) a[i] = x[i];
	for(int i = 0; i < y.size(); i++) b[i] = y[i];
	return query(min(v, (int)x.size()), y.size(), a, b);
	return 1;
}
void findroad(int s) {
	for(int t = 0, i = 1; i <= n; i++) {
		if(d.par(i)==i) d.paint(i, t++);
	}
	int X = 1;
	vi a[2];
	while(X < s) {
		a[0].clear(), a[1].clear();
		for(int i = 1; i <= n; i++) {
			a[(d.col(i)&X)>0].pb(i);
		}
		if(q(a[0], a[1])) break;
		X<<=1;
	}
	int x = 0, y = 0;
	for(int i = 1<<7; i>>=1;) {
		if(x+i<a[0].size()&&!q(a[0], a[1], x+i))
			x+=i;
	}
	for(int i = 1<<7; i>>=1;) {
		if(y+i<a[1].size()&&!q(a[1], a[0], y+i))
			y+=i;
	}
	x = a[0][x];
	y = a[1][y];
	d.unite(x, y);
	setRoad(x, y);
	//exit(0);//REMOVE THIS
}
void run(int _n) {
	n = _n;
	d.init(n);
	for(int p = 1; p < n; p++) {
		findroad(n-p+1);
	}
}

#ifdef kostia
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << "kostia:\n";
	int x, y;
	cin >> local_n >> x >> y;
	local_roads.pb({x, y});
	local_cur = 1;
	run(local_n);
	return 0;
}
#endif

Compilation message

icc.cpp: In function 'int q(vi, vi, int)':
icc.cpp:83:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < y.size(); i++) b[i] = y[i];
                 ~~^~~~~~~~~~
icc.cpp: In function 'void findroad(int)':
icc.cpp:103:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(x+i<a[0].size()&&!q(a[0], a[1], x+i))
      ~~~^~~~~~~~~~~~
icc.cpp:107:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(y+i<a[1].size()&&!q(a[1], a[0], y+i))
      ~~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 504 KB Ok! 101 queries used.
2 Correct 12 ms 504 KB Ok! 99 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 504 KB Ok! 544 queries used.
2 Correct 56 ms 568 KB Ok! 639 queries used.
3 Correct 61 ms 504 KB Ok! 663 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 632 KB Ok! 1426 queries used.
2 Correct 167 ms 504 KB Ok! 1544 queries used.
3 Correct 165 ms 504 KB Ok! 1577 queries used.
4 Correct 179 ms 504 KB Ok! 1564 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 616 KB Ok! 1502 queries used.
2 Correct 170 ms 504 KB Ok! 1578 queries used.
3 Correct 167 ms 504 KB Ok! 1578 queries used.
4 Correct 164 ms 504 KB Ok! 1507 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 632 KB Ok! 1605 queries used.
2 Correct 181 ms 504 KB Ok! 1576 queries used.
3 Correct 175 ms 504 KB Ok! 1627 queries used.
4 Correct 170 ms 632 KB Ok! 1605 queries used.
5 Correct 164 ms 632 KB Ok! 1496 queries used.
6 Correct 166 ms 504 KB Ok! 1587 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 632 KB Ok! 1571 queries used.
2 Correct 187 ms 504 KB Ok! 1598 queries used.