Submission #1163455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163455		tosivanmak	도시들 (IOI15_towns)	C++20	25 / 100	10 ms	584 KiB

towns

#include<bits/stdc++.h>
#include "towns.h"
using namespace std;
#define ll long long


static int _N;
static int _dist[110][110];
static int _quota, _user_query;

// void _ini_query(int N, int k) {
//     int ret;
//     _N = N;
//     for (int i = 0; i < _N; i++) 
//         for (int j = 0; j < _N; j++)  {
// 	    ret = scanf("%d", &_dist[i][j]);
//             assert(ret == 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++;
//     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];
// }

struct DSU{
    vector<ll>fa,siz;
    void init(ll n){
        fa.resize(n+5); siz.resize(n+5);
        for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;
    }
    ll root(ll x){
        if(fa[x]==x)return x;
        return fa[x]=root(fa[x]);
    }
    void unite(ll u, ll v){
        u=root(u); v=root(v);
        if(u==v)return;
        if(siz[u]<siz[v])swap(u,v);
        siz[u]+=siz[v]; fa[v]=u;
    }
};
bool asked[150][150];
ll dist[150][150];

int get(int i, int j){
    if(i==j){
        dist[i][j]=0; asked[i][j]=1;
        return dist[i][j];
    }
    if(asked[i][j]){
        return dist[i][j];
    }
    dist[i][j]=dist[j][i]=getDistance(i,j);
    asked[i][j]=asked[j][i]=1;
    return dist[i][j];
}
int hubDistance(int N, int sub){
    // getDistance(i, j)
    for(int i=0;i<150;i++){
        for(int j=0;j<150;j++){
            asked[i][j]=0;
        }
    }
    ll initial[150];
    for(int i=0;i<N;i++){
        initial[i]=get(0,i);
    }
    ll fur=-1,nd=-1;
    for(int i=0;i<N;i++){
        if(initial[i]>fur){
            fur=initial[i]; nd=i;
        }
    }
    ll dia[150];
    for(int i=0;i<N;i++){
        dia[i]=get(nd,i);
    }
    ll fur2=-1,nd2=-1;
    for(int i=0;i<N;i++){
        if(dia[i]>fur2){
            fur2=dia[i]; nd2=i;
        }
    }
    // nd,nd2 forms the diameter
    // how far away from nd
    ll dep[155];
    dep[nd]=0; dep[nd2]=0;
    ll diameter=get(nd,nd2);
    dep[0]=get(0,nd)+get(0,nd2)-diameter;
    dep[0]/=2;
    ll fromnd=get(0,nd)-dep[0];
    ll fromnd2=get(0,nd2)-dep[0];
    bool notuse[N+5];
    for(int i=0;i<N;i++){
        ll diff=get(0,i)+get(i,nd)-get(0,nd);
        ll req=(diff+2*fromnd);
        if(req==2*get(nd,i)){
            // closer to nd2
            notuse[i]=1;
        }
        else{
            notuse[i]=0;
            ll tryy=diff/2;
            ll chn=get(i,nd)-tryy;
            if(chn>fromnd){
                chn=get(0,nd)-dep[0];
                dep[i]=get(i,nd)-chn;
            }
            else{
                dep[i]=tryy;
            }
        }
        // dep[i]=(get(nd2,i)+get(nd,i)-diameter)/2;
    }
    ll dis[N+5];
    vector<ll>dists;
    for(int i=0;i<N;i++){
        if(!notuse[i])dists.push_back(get(nd,i)-dep[i]);
        if(!notuse[i])dis[i]=get(nd,i)-dep[i];
        else dis[i]=fromnd;
    }
    sort(dists.begin(),dists.end());
    dists.erase(unique(dists.begin(),dists.end()),dists.end());
    ll ans=1e18; vector<ll>cand;
    for(int i=0;i<dists.size();i++){
        ll val=max(dists[i],diameter-dists[i]);
        if(val<ans){
            cand.clear();
            ans=val;
            cand.push_back(dists[i]);
        }
        else if(val==ans){
            cand.push_back(dists[i]);
        }
    }
    bool ok=0;
    for(auto& u: cand){
        ll cnt=0;
        for(int i=0;i<N;i++){
            if(dis[i]==u){
                cnt++;
            }
        }
        ll smol=0,lar=0;
        if(cnt<=N/2){
            // no checking 
            for(int i=0;i<N;i++){
                if(dis[i]<u)smol++;
                else if(dis[i]>u)lar++;
            }
            if(smol<=N/2&&lar<=N/2)ok=1;
        }
        else{
            // since cnt > N/2 others <= N/2
            vector<ll>req;
            req.push_back(0);
            for(int i=0;i<N;i++){
                if(dis[i]==u)req.push_back(i);
            }
            DSU d;
            d.init(req.size());
            bool used[req.size()+5];
            for(int i=0;i<req.size()+5;i++)used[i]=0;
            ll ptrl=1,ptrr=1;
            while(ptrr<req.size()){
                if(ptrl==ptrr){ptrr++; continue;}
                if(used[ptrr]){ptrr++; continue;}
                if(used[ptrl]){ptrl++; continue;}
                ll dt=get(req[ptrl],req[ptrr]);
                ll real=dep[req[ptrl]]+dep[req[ptrr]];
                if(real==dt){
                    used[ptrl]=used[ptrr]=1; ptrl++; ptrr++;
                }
                else{
                    d.unite(ptrl,ptrr); ptrr++;
                }
            }
            ll id=-1;
            vector<ll>alll;
            for(int i=1;i<req.size();i++){
                if(!used[i]){
                    alll.push_back(i);
                }
            }
            if(alll.size()==0){
                ok=1; break;
            }
            else{
                for(int i=0;i<alll.size()-1;i++){
                    assert(d.root(alll[i])==d.root(alll[i+1]));
                }
                id=alll[0];
            }
            for(int i=1;i<req.size();i++){
                if(d.root(i)!=d.root(id)&&d.root(i)==i){
                    ll dt=get(req[i],req[id]);
                    ll real=dep[req[id]]+dep[req[i]];
                    if(dt!=real){
                        d.unite(i,id);
                    }
                }
            }
            if(d.siz[d.root(id)]<=N/2)ok=1;
        }
    }
    if(ok)return ans;
    else return -ans;
}

// int main() {
//     int ncase, R, N;
//     int subtask;
//     int ret;
//     ret = scanf("%d%d",&subtask,&ncase);
//     assert(ret == 2);
//     for (int i = 0; i < ncase; i++) {
//         ret = scanf("%d",&N);
// 	assert(ret == 1);
//         _ini_query(N,subtask);
//         R=hubDistance(N,subtask);
//         printf("%d\n",R);
//     }
//     return 0;
// }

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39