| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58586 |
2018-07-18T10:29:41 Z |
ruhanhabib39 |
ICC (CEOI16_icc) |
C++17 |
|
400 ms |
780 KB |
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
// query(|A|,|B|,A,B) (A, B) disjoint, returns whether there's an edge between A, B
// setRoad(u,v) tells there's an edge u--v
namespace {
int par[100 + 10];
vector<int> st[100 + 10];
vector<int> sts;
int N;
void init(int N_) {
N = N_; sts.reserve(N);
for(int i = 1; i <= N; i++) {
par[i] = i;
st[i].push_back(i);
sts.push_back(i);
}
}
int find(int u) {
if(par[u] == u) return u;
return par[u] = find(par[u]);
}
void merge(int u, int v) {
u = find(u); v = find(v);
if(u == v) return;
if(st[v].size() > st[u].size()) {
swap(v, u);
}
par[v] = u;
st[u].insert(st[u].end(), st[v].begin(), st[v].end());
sort(st[u].begin(), st[u].end());
st[u].resize(unique(st[u].begin(), st[u].end()) - st[u].begin());
sts.erase(find(sts.begin(), sts.end(), v));
cerr << "merge(" << u << ", " << v << ")\n";
}
vector<int> build(int l, int r) {
vector<int> rs;
for(int i = l; i <= r; i++) {
rs.insert(rs.end(), st[sts[i]].begin(), st[sts[i]].end());
}
return rs;
}
vector<int> get(vector<int> v, int l, int r) {
vector<int> rs(v.begin() + l, v.begin() + r + 1);
return rs;
}
bool hasEdge(int al, int ar, int bl, int br) {
auto A = build(al, ar); auto B = build(bl, br);
bool rs = query(A.size(), B.size(), A.data(), B.data());
return rs;
}
void superPinPoint(int u, int v) {
//cerr << "superPinPoint(" << u << ", " << v << ")\n";
auto A = st[u]; auto B = st[v];
while(A.size() > 1) {
//cerr << "|A| = " << A.size() << "\n";
int m = (A.size() - 1)/ 2;
//cerr << "m = " << m << "\n";
auto AA = get(A, 0, m);
//cerr << "|AA| = " << AA.size() << "\n";
if(query(AA.size(), B.size(), AA.data(), B.data())) A = AA;
else A = get(A, m+1, A.size()-1);
}
while(B.size() > 1) {
int m = (B.size() - 1) / 2;
auto BB = get(B, 0, m);
if(query(A.size(), BB.size(), A.data(), BB.data())) B = BB;
else B = get(B, m+1, B.size()-1);
}
setRoad(A[0], B[0]);
}
void pinpointEdge(int l0, int r0, int l1, int r1) {
//cerr << "pinpointing\n";
//cerr << "[" << l0 << ", " << r0 << "]\n";
while(l0 < r0) {
//cerr << "left[" << l0 << ", " << r0 << "]\n";
int m = (l0 + r0) / 2;
if(hasEdge(l0,m,l1,r1)) r0 = m;
else l0 = m + 1;
}
while(l1 < r1) {
int m = (l1 + r1) / 2;
if(hasEdge(l0,r0,l1,m)) r1 = m;
else l1 = m + 1;
}
int u = sts[l0], v = sts[l1];
superPinPoint(u, v);
merge(u, v);
}
bool findEdge(int l, int r) {
if(l >= r) return false;
int m = (l + r) / 2;
if(hasEdge(l,m,m+1, r)) {
pinpointEdge(l, m, m+1, r);
return true;
}
return findEdge(l, m) or findEdge(m+1, r);
}
};
void run(int n) {
init(n);
for(int i = 0; i < n-1; i++) {
findEdge(0,sts.size()-1);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
504 KB |
Program is not terminated properly. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
744 KB |
Program is not terminated properly. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
400 ms |
744 KB |
Program is not terminated properly. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
338 ms |
748 KB |
Program is not terminated properly. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
304 ms |
756 KB |
Program is not terminated properly. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
347 ms |
780 KB |
Program is not terminated properly. |
| 2 |
Halted |
0 ms |
0 KB |
- |
