| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 95173 | jasony123123 | ICC (CEOI16_icc) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include "icc.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
void io() {
#ifdef LOCAL_PROJECT
freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
#endif
ios_base::sync_with_stdio(false); cin.tie(NULL);
}
const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/******************************CEOI 2016 Day 1 P1 - ICC*********************************/
v<int> adj[101];
v<v<int>> comp;
int N, M;
//void setRoad(int a, int b);
//int query(int size_a, int size_b, int a[], int b[]);
v<int> unpack(v<int> &compA) {
v<int> nodeA;
for (auto c : compA) for (auto x : comp[c])
nodeA.push_back(x);
return nodeA;
}
int queryNodes(v<int> &nodeA, v<int> &nodeB) {
return query(nodeA.size(), nodeB.size(), nodeA.data, nodeB.data);
}
int queryComp(v<int> &compA, v<int> &compB) {
return queryNodes(unpack(compA), unpack(compB));
}
void dfs(int x, v<bool> &vis, v<int> &rec) {
if (vis[x]) return;
vis[x] = 1;
rec.push_back(x);
for (auto c : adj[x]) dfs(c, vis, rec);
}
void updComp() {
v<bool> vis(N + 1, 0);
comp.clear();
FORE(i, 1, N) if (!vis[i]) {
comp.push_back(v<int>());
dfs(i, vis, comp.back());
}
M = comp.size();
}
void findConnectComp(v<int> &compA, v<int> &compB) {
FOR(b, 0, 8) {
v<int> ca, cb;
FOR(i, 0, M) {
if (i&(1 << b)) ca.push_back(i);
else cb.push_back(i);
}
if (!ca.empty() && !cb.empty() && queryComp(ca, cb)) {
compA = ca, compB = cb;
return;
}
}
}
void reduce(v<int> &noa, v<int> &nob) {
while (nob.size() > 1) {
v<int> top, bot;
int mid = (0 + nob.size() - 1) / 2;
FORE(i, 0, mid)
top.push_back(nob[i]);
FORE(i, mid + 1, nob.size() - 1)
bot.push_back(nob[i]);
if (queryNodes(noa, top))
nob = top;
else
nob = bot;
}
}
void run(int n) {
N = n;
FOR(r, 0, n - 1) {
updComp();
v<int> compA, compB;
findConnectComp(compA, compB);
v<int> nodeA = unpack(compA);
v<int> nodeB = unpack(compB);
reduce(nodeA, nodeB);
reduce(nodeB, nodeA);
setRoad(nodeA[0], nodeB[0]);
adj[nodeA[0]].push_back(nodeB[0]);
adj[nodeB[0]].push_back(nodeA[0]);
}
}
//int main();