| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 533985 | iulia13 | Meetings (JOI19_meetings) | C++14 | 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.
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
const int N = 2005;
int vc[N];
int viz[N]; ///noduri 0... n - 1
vector <int> g[N];
int nxt[N];
int prv[N];
int cod[N];
int decod[N];
int subarb[N];
int intree[N];
void dfsSize(int nod, int dad = 0)
{
subarb[nod] = 1;
for (auto x : g[nod])
{
if (viz[x] || dad == x)
continue;
dfsSize(x, nod);
subarb[nod] += subarb[x];
}
}
int centroid(int nod, int dad, int newN)
{
for (auto x : g[nod])
{
if (viz[x] || dad == x)
continue;
if (subarb[x] > newN / 2)
return centroid(x, nod, newN);
}
return nod;
}
struct ura{
int x, sz;
} sons[20];
bool cmp(ura a, ura b)
{
return a.sz > b.sz;
}
int nrsons;
int compute_centroid(int nod, int newN)
{
dfsSize(nod, 0);
int root = centroid(nod, 0, newN);
dfsSize(root, 0);
nrsons = 0;
for (auto x : g[root])
sons[++nrsons] = {x, subarb[x]};
sort(sons + 1, sons + nrsons + 1, cmp);
return root;
}
void rupe(int a, int b, int c)
{
for (auto &x : g[a])
if (x == b)
{
x = c;
break;
}
for (auto &x : g[b])
if (x == a)
{
x = c;
break;
}
g[c].push_back(a);
g[c].push_back(b);
}
/*int Query(int a, int b, int c)
{
cout << a << " " << b << " " << c;
cin >> a;
return a;
}
void Bridge(int u, int v)
{
cout << u << " " << v << endl;
}*/
void solve(int n)
{
int nodes = 0;
for (int i = 0; i < n; i++)
nxt[i] = i + 1;
for (int i = 1; i <= n; i++)
prv[i] = i - 1;
for (int i = 1; i <= n && nodes < n; i++)
{
int j = rand() % n + 1, cnt = 0;
while (intree[j] && cnt <= 500)
{
cnt++;
j = rand() % n + 1;
}
if (intree[j])
j = nxt[0];
int p = prv[j];
int q = nxt[j];
intree[j] = 1;
prv[q] = p;
nxt[p] = q;
for (int hh = 1; hh <= nodes; hh++)
viz[hh] = 0;
nodes++;
cod[j] = nodes;
decod[nodes] = j - 1;
int myn = nodes;
int mynewnod = 1;
int nrnodes = nodes - 1;
if (!nrnodes)
continue;
while(true)
{
auto root = compute_centroid(mynewnod, nrnodes);
if (nrsons == 0)
{
g[root].push_back(myn);
g[myn].push_back(root);
break;
}
int h = 1, ok = 0;
int nou = decod[myn];
int realroot = decod[root];
while (h + 1 <= nrsons && !ok)
{
int v1 = decod[sons[h].x];
int v2 = decod[sons[h + 1].x];
int ans = Query(v1, v2, nou);
if (ans == realroot) ///not important
h += 2;
else
if (ans == v1) ///subarb v1
{
ok = 2;
viz[root] = 1;
mynewnod = sons[h].x;
nrnodes = subarb[sons[h].x];
}
else
if (ans == v2)
{
ok = 2;
viz[root] = 1;
mynewnod = sons[h + 1].x;
nrnodes = subarb[sons[h].x];
}
else
if (ans == nou)
{
ok = 1;
if (Query(v1, realroot, nou) == nou)
rupe(root, sons[h].x, myn);
else
rupe(root, sons[h + 1].x, myn);
}
else
{
ok = 1;
nodes++;
intree[nodes] = 1;
decod[nodes] = ans;
cod[ans] = nodes;
if (Query(v1, realroot, ans) == ans)
rupe(root, sons[h].x, nodes);
else
rupe(root, sons[h + 1].x, nodes);
g[nodes].push_back(myn);
g[myn].push_back(nodes);
}
}
if (h == nrsons && !ok)
{
int v1 = decod[sons[h].x];
int answ = Query(v1, realroot, nou);
if (answ != realroot)
{
if (answ == v1)
{
ok = 2;
mynewnod = sons[h].x;
viz[root] = 1;
nrnodes = subarb[sons[h].x];
}
else
if (answ == nou)
{
ok = 1;
rupe(root, sons[h].x, myn);
}
else
{
ok = 1;
nodes++;
intree[nodes] = 1;
decod[nodes] = answ;
rupe(root, sons[h].x, nodes);
g[nodes].push_back(myn);
g[myn].push_back(nodes);
}
}
}
if (ok == 0)
{
ok = 1;
g[myn].push_back(root);
g[root].push_back(myn);
}
if (ok != 2)
break;
}
}
for (int i = 1; i <= n; i++)
{
for (auto j : g[i])
{
if (decod[i] < decod[j])
Bridge(decod[i], decod[j]);
}
}
}/*
int main()
{
int n;
cin >> n;
solve(n);
return 0;
}
*/