oj.uz

Submission #17288

# Submission time Handle Problem Language Result Execution time Memory
17288 2015-11-11T20:02:55 Z ainta Towns (IOI15_towns) C++
100 / 100
 24 ms 1140 KB 
#include "towns.h"
#include<algorithm>
using namespace std;
#define pii pair<int,int>

#define N_ 120
#define INF 999999999

int D1[N_], D2[N_], w[10][N_], UF[N_], ddis, n, p1, p2;
bool chk[10][N_];
int v[N_], ckk;

bool Same(int a, int b){
    int d = getDistance(a,b);
    if(d!=D2[a]+D2[b]-ddis*2)return true;
    return false;
}

int Find(int a){
    if(a==UF[a])return a;
    return UF[a]=Find(UF[a]);
}

pii Do(int pv, int cnt){
    int i, cc = 0, C, x, t;
    if(cnt == 1){
        return pii(w[pv][0],1);
    }
    for(i=0;i<cnt/2;i++){
        if(Same(w[pv][i*2],w[pv][i*2+1])){
            UF[w[pv][i*2+1]] = w[pv][i*2];
            w[pv+1][cc] = w[pv][i*2];
            chk[pv][i]=true;
            cc++;
        }
        else chk[pv][i]=false;
    }
    pii r = pii(0,0);
    if(cc)r = Do(pv+1,cc);
    C = r.second*2, x = r.first;
    if(cnt%2==0){
        if(r.second==0)return pii(0,0);
        for(i=0;i<cnt/2;i++){
            if(chk[pv][i])continue;
            if(Same(x, w[pv][i*2]))C++;
            if(Same(x, w[pv][i*2+1]))C++;
        }
        if(C*2>cnt)return pii(x,C);
        return pii(0,0);
    }
    if(C){
        for(i=0;i<cnt/2;i++){
            if(chk[pv][i])continue;
            if(Same(x, w[pv][i*2]))C++;
            if(Same(x, w[pv][i*2+1]))C++;
        }
        if(Same(x, w[pv][cnt-1]))C++;
        if(C*2>cnt)return pii(x,C);
        return pii(0,0);
    }
    x = w[pv][cnt-1], C = 1;
    for(i=0;i<n;i++)v[i]=0;
    for(i=0;i<cnt-1;i++){
        t = Find(w[pv][i]);
        if(!v[t]){
            if(Same(x,w[pv][i])){
                C++;
                v[t]=2;
            }
            else v[t]=1;
        }
        else C+=v[t]-1;
    }
    if(C*2>cnt)return pii(x,C);
    return pii(0,0);
}

bool Pos(int N, int d){
    int i, c1 = 0, c2 = 0, t, cnt = 0;
    for(i=0;i<N;i++){
        t = D2[i] - (D1[i]+D2[i]-D1[p1])/2;
        if(t < d) c1++;
        else if(t > d) c2++;
        else w[0][cnt++] = i;
    }
    if(c1>N/2||c2>N/2)return false;
    if(ckk)return false;
    ckk = 1;
    for(i=0;i<N;i++)UF[i]=i;
    ddis = d;
    if(Do(0,cnt).second*2>N)return false;
    return true;
}

int hubDistance(int N, int sub) {
    n = N;
    int i, M = -1, R, t, dd;
    D1[0]=0;
    for(i=1;i<N;i++){
        D1[i] = getDistance(0,i);
        if(M<D1[i])M=D1[i],p1=i;
    }
    M=-1;
    D2[p1]=0;
    for(i=0;i<N;i++){
        if(i!=p1) D2[i] = getDistance(p1,i);
        if(M<D2[i])M=D2[i],p2=i;
    }
    dd = (D1[p1] + D2[p2] - D1[p2])/2;
    R = INF;
    for(i=0;i<N;i++){
        t = D2[i]-(D1[i]+D2[i]-D1[p1])/2;
        if(t <= dd){
            R = min(R, max(t,D2[p2]-t));
        }
    }
    ckk = 0;
    for(i=0;i<N;i++){
        t = D2[i]-(D1[i]+D2[i]-D1[p1])/2;
        if(t <= dd){
            if(max(t,D2[p2]-t) == R && Pos(N, t))return R;
        }
    }
    return -R;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1140 KB Output is correct
2 Correct 0 ms 1140 KB Output is correct
3 Correct 0 ms 1140 KB Output is correct
4 Correct 22 ms 1140 KB Output is correct
5 Correct 23 ms 1140 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1140 KB Output is correct
2 Correct 10 ms 1140 KB Output is correct
3 Correct 14 ms 1140 KB Output is correct
4 Correct 19 ms 1140 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1140 KB Output is correct
2 Correct 23 ms 1140 KB Output is correct
3 Correct 0 ms 1140 KB Output is correct
4 Correct 24 ms 1140 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1140 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1140 KB Output is correct
2 Correct 8 ms 1140 KB Output is correct
3 Correct 22 ms 1140 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1140 KB Output is correct
2 Correct 13 ms 1140 KB Output is correct
3 Correct 24 ms 1140 KB Output is correct