oj.uz

Submission #331060

# Submission time Handle Problem Language Result Execution time Memory
331060 2020-11-27T07:59:49 Z IloveN Towns (IOI15_towns) C++14
48 / 100
 28 ms 768 KB 
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
#include "towns.h"

const int N=1e3+10;
namespace myrand
{
    mt19937 mt(chrono::system_clock::now().time_since_epoch() / chrono::microseconds(1));
    ll Int(ll l,ll r) { return uniform_int_distribution<ll> (l,r)(mt);}
}

using namespace myrand;

/*int getDistance(int x,int y)
{
    return 0;
}*/

int dis[N][N];
int lim;

int get(int x,int y)
{
    if (x==y) return 0;
    if (dis[x][y]) return dis[x][y];
    lim--;
    return (dis[x][y]=dis[y][x]=getDistance(x-1,y-1));
}

int rng(int x) {return Int(0,x-1);}

bool check_balance(vi &lc,int x,int n,int sub,int s)
{
    vi vt;
    int siz1=0,siz2=0,siz3=0;
    for (int i=1;i<=n;i++)
        if (lc[i]<x) siz1++;
        else if (lc[i]==x) siz2++,vt.eb(i);
        else siz3++;
    if (max(siz1,siz3)>n/2) return false;
    if (sub==4) return (siz2<=n/2);
    if (sub!=3)
    {
        while (lim>0)
        {
            random_shuffle(all(vt),rng);
            vi vt2;
            int k=vt.back();
            vt.pop_back();
            int len=1;
            while (!vt.empty() && (int)vt.size()+len>n/2)
            {
                if (lim==0) return true;
                int h=vt.back();
                vt.pop_back();
                if (get(k,h)<dis[s][h]+dis[s][k]-2*x) len++;
                else vt2.eb(h);
                if (len>n/2) return false;
            }
            for (int h : vt2) vt.eb(h);
        }
        return true;
    }
    for (int i : vt)
    {
        int cnt=0;
        for (int j : vt)
            if (get(i,j)<dis[s][i]+dis[s][j]-2*x) cnt++;
        if (cnt>n/2) return false;
    }
    return true;
}

int hubDistance(int n, int sub)
{
	if (sub==1 || sub==3) lim=n*(n-1)/2;
	else if (sub==5) lim=5*n;
	else lim=(7*n+1)/2;
	int s=Int(1,n),t=0,mx=0;
	for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++) dis[i][j]=0;
	for (int i=1;i<=n;i++)
    if (s!=i)
    {
        int d=get(s,i);
        if (d>mx) mx=d,t=i;
    }
    for (int i=1;i<=n;i++)
    if (i!=t)
    {
        int d=get(t,i);
        dis[t][i]=d;
        if (d>mx) mx=d,s=i;
    }
    int res=mx,flag=0;
    vi lc(n+1);
    for (int i=1;i<=n;i++)
    if (i!=s && i!=t)
    {
        int d=get(s,i);
        int tmp=(d+dis[t][i]-dis[t][s])/2;
        res=min(res,max(d-tmp,dis[t][i]-tmp));
    }
    for (int i=1;i<=n;i++)
    {
        int d=(dis[s][i]+dis[t][i]-dis[s][t])/2;
        if (dis[t][i]-d==res) flag |= 1;
        if (dis[s][i]-d==res) flag |= 2;
        lc[i]=dis[s][i]-d;
    }
    if (sub<3) return res;
    if (flag&1 && check_balance(lc,mx-res,n,sub,s)) return res;
    if ((flag>>1)&1 && check_balance(lc,res,n,sub,s)) return res;
    return -res;
}

/*int main()
{
    //freopen("ss.inp","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}*/

Compilation message

towns.cpp: In function 'int rng(int)':
towns.cpp:42:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 | int rng(int x) {return Int(0,x-1);}
      |                        ~~~^~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:91:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |  int s=Int(1,n),t=0,mx=0;
      |        ~~~^~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 748 KB Output is correct
2 Correct 17 ms 748 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 22 ms 768 KB Output is correct
5 Correct 23 ms 748 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 748 KB Output is correct
2 Correct 16 ms 748 KB Output is correct
3 Correct 28 ms 748 KB Output is correct
4 Correct 24 ms 748 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 748 KB Output is correct
2 Correct 22 ms 748 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 24 ms 748 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 748 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -