oj.uz

Submission #17289

# Submission time Handle Problem Language Result Execution time Memory
17289 2015-11-12T04:36:52 Z ainta Towns (IOI15_towns) C++
100 / 100
 25 ms 1148 KB 
#include "towns.h"
#include<algorithm>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second

#define N_ 120
#define INF 999999999

int D1[N_], D2[N_], ddis, n, p1, p2;
pii w[15][N_];
bool chk[15][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;
}

pii Do(int pv, int cnt){
    int i, cc = 0, t;
    if(cnt == 1)return w[pv][0];
    for(i=0;i<cnt/2;i++){
        chk[pv][i]=false;
        if(Same(w[pv][i*2].X,w[pv][i*2+1].X)){
            w[pv+1][cc] = w[pv][i*2];
            w[pv+1][cc].Y += w[pv][i*2+1].Y;
            cc++;
        }
        else{
            chk[pv][i]=true;
            if(w[pv][i*2].Y>w[pv][i*2+1].Y){
                w[pv+1][cc] = w[pv][i*2];
                w[pv+1][cc].Y -= w[pv][i*2+1].Y;
                cc++;
            }
            else if(w[pv][i*2].Y<w[pv][i*2+1].Y){
                w[pv+1][cc] = w[pv][i*2+1];
                w[pv+1][cc].Y -= w[pv][i*2].Y;
                cc++;
            }
        }
    }
    if(cnt%2==1){
        w[pv+1][cc] = w[pv][cnt-1];
        cc++;
    }
    pii r = pii(0,0);
    if(cc)r = Do(pv+1,cc);
    if(r.Y==0)return r;
    for(i=0;i<cnt/2;i++){
        if(chk[pv][i]){
            t = min(w[pv][i*2].Y,w[pv][i*2+1].Y);
            if(Same(w[pv][i*2].X,r.X))r.Y+=t;
            else r.Y-=t;
            if(Same(w[pv][i*2+1].X,r.X))r.Y+=t;
            else r.Y-=t;
        }
    }
    if(r.Y>0)return r;
    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++] = pii(i,1);
    }
    if(c1>N/2||c2>N/2)return false;
    if(ckk)return false;
    ckk = 1;
    ddis = d;
    if((Do(0,cnt).Y + cnt) > 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 1148 KB Output is correct
2 Correct 11 ms 1148 KB Output is correct
3 Correct 0 ms 1148 KB Output is correct
4 Correct 0 ms 1148 KB Output is correct
5 Correct 15 ms 1148 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1148 KB Output is correct
2 Correct 20 ms 1148 KB Output is correct
3 Correct 0 ms 1148 KB Output is correct
4 Correct 18 ms 1148 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1148 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1148 KB Output is correct
2 Correct 12 ms 1148 KB Output is correct
3 Correct 23 ms 1148 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1148 KB Output is correct
2 Correct 25 ms 1148 KB Output is correct
3 Correct 0 ms 1148 KB Output is correct