| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 761848 | Red_Inside | Towns (IOI15_towns) | C++17 | 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 "towns.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <bits/stdc++.h>
#include <time.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=1e6+10,LOG=17,mod=1e9+7;
int block = 340, timer = 0;
const double eps = 1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define bt(i) (1 << (i))
//#define int ll
const int inf=2e9+10;
#define y1 yy
#define prev pre
#define pii pair <int, int>
int n, have, dist[500][500], cnt;
vector <pair <pii, int> > edges;
vector <pii> edge[maxn];
int getdist(int v, int u)
{
if(v == u) return 0;
if(dist[v][u] != -1) return dist[v][u];
dist[v][u] = getDistance(v, u);
dist[u][v] = dist[v][u];
return dist[v][u];
}
void solve(int pred, int V, vector <pii> ver)
{
// cout << "SOLVE " << pred << " " << V << endl;
// for(auto i : ver) cout << i.f << " ";
// cout << endl;
int mn = inf;
for(auto v : ver)
{
for(auto u : ver)
{
if(v.s + u.s - getdist(v.f, u.f) < mn)
{
mn = v.s + u.s - getdist(v.f, u.f);
}
}
}
mn /= 2;
edges.pb({{V, pred}, mn});
vector <vector <pii> > seg;
while(ver.size())
{
int v = ver.back().f;
int d1 = ver.back().s;
ver.pop_back();
vector <pii> nw, seg;
seg.pb({v,d1});
for(auto i : ver)
{
if((i.s+d1-getdist(i.f, v))/2 == mn) nw.pb(i);
else
seg.pb(i);
}
// cout << "NEW SEG for " << V << endl;
// for(auto i : seg) cout << i.f << " ";
// cout << endl;
ver = nw;
FOR(0, i, seg.size()) seg[i].s -= mn;
if(seg.size() == 1)
edges.pb({{V, seg[0].f}, seg[0].s});
else
solve(V, ++cnt, seg);
}
}
int sz[maxn], deep[maxn];
ll mxdist[maxn];
ll dpup[maxn];
void dfs(int v, int pred)
{
if(edge[v].size() == 1)
sz[v] = 1;
else
sz[v] = 0;
mxdist[v] = 0;
dpup[v] = 0;
for(auto to : edge[v])
{
if(to.f == pred) continue;
deep[to.f] = deep[v] + to.s;
dfs(to.f, v);
mxdist[v] = max(mxdist[v], mxdist[to.f] + to.s);
sz[v] += sz[to.f];
}
}
void dfs2(int v, int pred = -1)
{
vector <ll> pref(edge[v].size()), suff(edge[v].size());
pref[0] = (edge[v][0].f == pred ? 0 : mxdist[edge[v][0].f] + edge[v][0].s);
FOR(1, i, edge[v].size())
{
pref[i] = pref[i - 1];
if(edge[v][i].f == pred) continue;
pref[i] = max(pref[i], mxdist[edge[v][i].f] + edge[v][i].s);
}
suff[(int)edge[v].size() - 1] = (edge[v].back().f == pred ? 0 : mxdist[edge[v].back().f] + edge[v].back().s);
for(int i = (int)edge[v].size() - 2; i >= 0; --i)
{
suff[i] = suff[i + 1];
if(edge[v][i].f == pred) continue;
suff[i] = max(suff[i], mxdist[edge[v][i].f] + edge[v][i].s);
}
FOR(0, i, edge[v].size())
{
pii to = edge[v][i];
if(to.f == pred) continue;
dpup[to.f] = to.s+max({dpup[v], (i>0?pref[i-1]:0), (i+1<(int)edge[v].size()?suff[i+1]:0)});
dfs2(to.f, v);
}
}
int hubDistance(int n, int sub)
{
have = 0;
forn(0, i, n-1)
{
forn(0, j, n-1)
{
dist[i][j] = -1;
}
}
edges.clear();
cnt = n-1;
vector <pii> vec;
forn(1, i, n-1)
{
vec.pb({i, getdist(0, i)});
}
solve(0, ++cnt, vec);
forn(0, i, cnt) edge[i].clear();
for(auto i : edges)
{
edge[i.f.f].pb({i.f.s, i.s});
edge[i.f.s].pb({i.f.f, i.s});
// cout << i.f.f << " " << i.f.s << " " << i.s << endl;
}
deep[0] = 0;
dfs(0, -1);
dfs2(0);
ll res = 1e18;
forn(n, i, cnt)
{
// cout << dpup[i] << " " << mxdist[i] << endl;
if(max(dpup[i], mxdist[i]) < res) res = max(dpup[i], mxdist[i]);
}
forn(n, i, cnt)
{
if(res == max(dpup[i], mxdist[i]))
{
int ok = 1;
for(auto to : edge[i])
{
if(sz[to.f] > sz[i])
{
if(n - sz[i] > n / 2) ok = 0;
}
else
{
if(sz[to.f] > n / 2) ok = 0;
}
}
if(ok)
{
have = 1;
}
}
}
return res * (have ? 1 : -1);
}
/*
1 1
4
0 35 44 31
35 0 29 16
44 29 0 21
31 16 21 0
*/
static int N;
static int Dist[333][333];
static int quota, user_query;
static int pid;
void ini_query(int n, int k) {
N = n;
for (int i = 0; i < (N); i++)
for (int j = 0; j < (N); j++) {
int r = scanf("%d", &Dist[i][j]);
assert(r == 1);
}
if (k == 1 || k == 3)
quota = (N) * ((N) - 1) / 2;
else if (k == 2 || k == 4 || k == 6)
quota = (7 * (N) + 1) / 2;
else
quota = 5 * (N);
user_query = 0;
}
int getDistance(int i, int j) {
user_query = user_query + 1;
if (user_query > quota) {
printf("0\n");
exit(0);
}
if (i < 0 || i >= N)
return 0;
if (j < 0 || j >= N)
return 0;
return Dist[i][j];
}
int main() {
int ncase, R, N;
int subtask;
scanf("%d%d", &subtask, &ncase);
for (int i = 0; i < ncase; i++) {
scanf("%d", &N);
ini_query(N, subtask);
R = hubDistance(N, subtask);
if (subtask < 3 && R < 0)
R = -R;
printf("%d\n", R);
}
return 0;
}