| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 203446 |
2020-02-20T16:52:33 Z |
kostia244 |
ICC (CEOI16_icc) |
C++17 |
|
493 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";
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;
void init(int n) {
r.resize(n+1);
p.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 n;
int a[maxn], b[maxn];
dsu d;
int q(vi x, vi y) {
if(x.empty()||y.empty()) return 0;
for(int i = 0; i < x.size(); i++) a[i] = x[i];
for(int i = 0; i < y.size(); i++) b[i] = y[i];
return query(x.size(), y.size(), a, b);
}
void run(int _n) {
n = _n;
d.init(n);
for(int p = 1; p < n; p++) {
int x = -1, y = -1;
for(int i = 1; i <= n; i++) {
vi t;
for(int j = 1; j <= n; j++) {
if(!d.con(i, j))
t.pb(j);
}
if(!q(vi{i}, t)) continue;
if(x==-1) x = i;
else if(y==-1) y = i;
else exit(255);
}
setRoad(x, y);
d.unite(x, y);
}
}
#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)':
icc.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < x.size(); i++) a[i] = x[i];
~~^~~~~~~~~~
icc.cpp:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < y.size(); i++) b[i] = y[i];
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
504 KB |
Ok! 210 queries used. |
| 2 |
Correct |
19 ms |
504 KB |
Ok! 210 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
195 ms |
504 KB |
Ok! 2450 queries used. |
| 2 |
Correct |
205 ms |
632 KB |
Ok! 2450 queries used. |
| 3 |
Correct |
195 ms |
504 KB |
Ok! 2450 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
493 ms |
560 KB |
Number of queries more than 4500 out of 2250 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
443 ms |
632 KB |
Number of queries more than 4000 out of 2000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
399 ms |
504 KB |
Number of queries more than 3550 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
364 ms |
632 KB |
Number of queries more than 3250 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
