oj.uz

Submission #731002

# Submission time Handle Problem Language Result Execution time Memory
731002 2023-04-26T18:25:08 Z Vu_CG_Coder Towns (IOI15_towns) C++14
48 / 100
 27 ms 852 KB 
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

int f[110][110];
// int getDistance(int x , int y){
//     return f[x][y];
// }

int sub1(int N,int sub){
    int n = N;
    pair <int,int> tmp;
    vector <int> val , value;
    val.assign(n,0);
    value.assign(n,0);
    for (int i = 1 ; i < n ; i++){
        int x = getDistance(0,i);
        tmp = max(tmp,make_pair(x,i));
    }

    int u = tmp.second;
    tmp.first = 0;
    for (int i = 0 ; i < n ; i++)
    if (i != u){
        int x = getDistance(i,u);
        val[i] = x;
        tmp = max(tmp,make_pair(x,i));
    }
    int v = tmp.second;
    int R = 1e9;
    for (int i = 0 ; i < n ; i++)
    if (i != u && i != v){
        int x = getDistance(v,i);
        value[i] = x;
        int y = val[i];
        int z = val[v];
        int a = (x + y - z)/2;
        int b = x - a;
        int c = z - b;
        int r = max(a,max(b,c));

        if (r < R){
            tmp = make_pair(b,c);
            R = r;
        }
    }

    if (sub < 3) return R;
    int cntu = 1 , cntv = 1 , cnt = 0;
    for (int i = 0 ; i < n ; i++) 
    if (i != u && i != v) 
    {
        int x = val[i];
        int y = val[v];
        int z = value[i];
        int a = (x + y - z)/2;
        if (a < tmp.second) cntu++;
        if (a == tmp.second) cnt++;
        if (a > tmp.second) cntv++;
    }
    if (cntu > n/2 || cntv > n/2 || cnt > n/2) return -R;
    return R; 
}

bool check(int u , int v , int tt , vector <vector<int> > &val,int n){
    int cntu = 1 , cntv = 1;
    vector <int> pt;
    for (int i = 0 ; i < n ; i++) 
    if (i != u && i != v) {
        int x = val[i][u];
        int y = val[v][u];
        int z = val[v][i];
        int a = (x + y - z)/2;
        if (a < tt) cntu++;
        if (a == tt) {
            pt.push_back(i);
        }
        if (a > tt) cntv++;
    }

    if (cntu > n/2 || cntv > n/2) return false;
    while (!pt.empty()){
        vector <int> kt;
        v = pt[0];
        int d = 1;
        for (int p : pt) if (p != v){
            int x = val[v][p];
            int y = val[v][u];
            int z = val[p][u];
            int a = (x + y - z)/2;
            int b = x - a;
            int c = z - b;

            if (c > tt) d++;
            else kt.push_back(p);
        }
        if (d > n/2) return false;
        pt = kt;
    }

    return true;
}

int sub3(int n){
    pair <int,int> tmp;
    vector <vector<int> > val;
    val.assign(n,vector<int>(n,0));

    for (int i = 0 ; i < n ; i++)
        for (int j = i + 1 ; j < n ; j++){
            int x = getDistance(i,j);
            val[i][j] = x;
            val[j][i] = x;
        }

    for (int i = 1 ; i < n ; i++){
        int x = val[0][i];
        tmp = max(tmp,make_pair(x,i));
    }

    int u = tmp.second;
    tmp.first = 0;
    for (int i = 0 ; i < n ; i++)
    if (i != u){
        int x = val[i][u];
        tmp = max(tmp,make_pair(x,i));
    }
    int v = tmp.second;
    vector <int> stp;
    int R = 1e9;
    for (int i = 0 ; i < n ; i++)
    if (i != u && i != v){
        int x = val[i][v];
        int y = val[u][i];
        int z = val[u][v];
        int a = (x + y - z)/2;
        int b = x - a;
        int c = z - b;
        int r = max(a,max(b,c));

        if (r < R){
            stp.clear();
            stp.push_back(c);
            R = r;
        }
        else 
        if (r == R) stp.push_back(c);
    }

    int ok = 0;
    for (int p : stp)
    if (check(u,v,p,val,n)) ok = 1;

    if (!ok) return -R;
    return R;
}

int hubDistance(int N, int sub) {
    if (sub < 3 || sub == 4) return sub1(N,sub);
    return sub3(N);
}

// int main(){
//     freopen("txt.inp","r",stdin);
//     freopen("txt.out","w",stdout);

//     int n;
//     cin >> n;
//     for (int i = 0 ; i < n ; i++)
//         for (int j = 0 ; j < n ; j++)
//             cin >> f[i][j];

//     cout << hubDistance(n,3);
//     return 0;
// }

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 344 KB Output is correct
2 Correct 16 ms 348 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 13 ms 344 KB Output is correct
5 Correct 14 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 340 KB Output is correct
2 Correct 12 ms 804 KB Output is correct
3 Correct 19 ms 840 KB Output is correct
4 Correct 18 ms 852 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 340 KB Output is correct
2 Correct 17 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 27 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 348 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -