oj.uz

Submission #69897

# Submission time Handle Problem Language Result Execution time Memory
69897 2018-08-21T20:58:28 Z wleung_bvg Towns (IOI15_towns) C
100 / 100
 40 ms 3280 KB 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
#include <stdbool.h>
#include <limits.h>
#include <time.h>
#include <assert.h>
#include <stdarg.h>
#include <stddef.h>
#include "towns.h"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define EPS 1e-9
// #define min(a,b) ((a)<(b)?(a):(b))
// #define max(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)=min((a),(b)))
#define MAX(a,b) ((a)=max((a),(b)))
#define For(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,b) For(i,0,b)
#define Rev(i,a,b) for(int i=(a);i>(b);i--)
#define REV(i,a) Rev(i,a,-1)
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;

#define _bufferSize 4096
#define _maxNumLength 128
char _inputBuffer[_bufferSize+1],*_inputPtr=_inputBuffer,_c,_sign;int _cur;
#define _peekchar() (*_inputPtr?*_inputPtr:(_inputBuffer[fread(_inputPtr=_inputBuffer,1,_bufferSize,stdin)]='\0',*_inputPtr))
#define _getchar() getchar()
#define _hasNext() (*_inputPtr||!feof(stdin))
#define _readSignAndNum(x) do{(x)=_getchar();}while((x)<=' ');_sign=(x)=='-';if(_sign)(x)=_getchar();for((x)-='0';(_c=_getchar())>='0';(x)=(x)*10+_c-'0')
#define _readFloatingPoint(x,T) for(T _div=1.0;(_c=_getchar())>='0';(x)+=(_c-'0')/(_div*=10))
#define rc(x) do{do{(x)=_getchar();}while((x)<=' ');}while(0)
#define ri(x) do{_readSignAndNum(x);if(_sign)(x)=-(x);}while(0)
#define rd(x) do{_readSignAndNum(x);if(_c=='.')_readFloatingPoint(x,double);if(_sign)(x)=-(x);}while(0)
#define rld(x) do{_readSignAndNum(x);if(_c=='.')_readFloatingPoint(x,ld);if(_sign)(x)=-(x);}while(0)
#define rcs(x) do{_cur=0;do{_c=_getchar();}while(_c<=' ');do{(x)[_cur++]=_c;}while((_c=_getchar())>' ');(x)[_cur]='\0';}while(0)
#define rcln(x) do{_cur=0;do{_c=_getchar();}while(_c<=' ');do{(x)[_cur++]=_c;}while((_c=_getchar())>=' ');(x)[_cur]='\0';}while(0)
int hasNext(){while(_hasNext()&&_peekchar()<=' ')_getchar();return _hasNext();}

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

#define MAXN 110

int N, qcnt = 0, distRoot[MAXN], distDiam[MAXN], distPath[MAXN], check[MAXN], checkSz = 0, neq[MAXN], candidates[MAXN], candidatesSz = 0;

// int getDistance(int i, int j) {
    // assert(0 <= i && i < N);
    // assert(0 <= j && j < N);
    // printf("? %d %d\n", i, j);
    // fflush(stdout);
    // int ans;
    // ri(ans);
    // return ans;
// }

int query(int i, int j) {
    if (++qcnt > (7 * N + 1) / 2) assert(0);
    return getDistance(i, j);
}

int hasMajority(int d) {
    int lt = 0, gt = 0, k = 0, cnt = 0;
    checkSz = candidatesSz = 0;
    FOR(i, N) {
        if (distDiam[i] - distPath[i] < d) lt++;
        else if (distDiam[i] - distPath[i] > d) gt++;
        else check[checkSz++] = i;
    }
    if (checkSz == 0 || lt > N / 2 || gt > N / 2) return 1;
    FOR(i, checkSz) {
        if (cnt == 0) {
            cnt++;
            candidates[candidatesSz++] = k = i;
        } else if (neq[i] = (query(check[i], check[k]) != distPath[check[i]] + distPath[check[k]])) cnt++;
        else cnt--;
    }
    cnt = (cnt + checkSz - k) / 2;
    FOR(i, candidatesSz - 1) {
        if (query(check[candidates[i]], check[k]) != distPath[check[candidates[i]]] + distPath[check[k]]) cnt += (candidates[i + 1] - candidates[i]) / 2;
        else For(j, candidates[i] + 1, candidates[i + 1]) if (!neq[j] && query(check[j], check[k]) != distPath[check[j]] + distPath[check[k]]) cnt++;
    }
    return cnt > N / 2;
}

int hubDistance(int n, int sub) {
    qcnt = 0;
    N = n;
    int diamV = 0, maxDist = distRoot[0] = 0, minPathDist = INT_INF;
    For(i, 1, N) {
        if (maxDist < (distRoot[i] = query(0, i))) {
            maxDist = distRoot[i];
            diamV = i;
        }
    }
    distDiam[diamV] = 0;
    distDiam[0] = maxDist;
    For(i, 1, N) if (i != diamV) MAX(maxDist, distDiam[i] = query(diamV, i));
    distPath[0] = distPath[diamV] = 0;
    For(i, 1, N) if (i != diamV) MIN(minPathDist, abs(maxDist - 2 * (distDiam[i] - (distPath[i] = (distRoot[i] + distDiam[i] - distDiam[0]) / 2))));
    return (hasMajority((maxDist + minPathDist) / 2) && (minPathDist == 0 || hasMajority((maxDist - minPathDist) / 2)) ? -1 : 1) * (maxDist + minPathDist) / 2;
}

// int main() {
    // // freopen("in.txt", "r", stdin);
    // // freopen("out.txt", "w", stdout);
    // ri(N);
    // int sub;
    // ri(sub);
    // printf("! %d\n", hubDistance(N, sub));
    // return 0;
// }

Compilation message

towns.c: In function 'hasMajority':
towns.c:80:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
         } else if (neq[i] = (query(check[i], check[k]) != distPath[check[i]] + distPath[check[k]])) cnt++;
                    ^~~
towns.c: In function 'hubDistance':
towns.c:91:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int n, int sub) {
                            ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 376 KB Output is correct
2 Correct 18 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 23 ms 512 KB Output is correct
5 Correct 23 ms 568 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 568 KB Output is correct
2 Correct 19 ms 1104 KB Output is correct
3 Correct 23 ms 1736 KB Output is correct
4 Correct 25 ms 2224 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2224 KB Output is correct
2 Correct 23 ms 2228 KB Output is correct
3 Correct 2 ms 2228 KB Output is correct
4 Correct 35 ms 2228 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2356 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2356 KB Output is correct
2 Correct 24 ms 2356 KB Output is correct
3 Correct 40 ms 2356 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2356 KB Output is correct
2 Correct 23 ms 2740 KB Output is correct
3 Correct 22 ms 3280 KB Output is correct