oj.uz

Submission #979367

# Submission time Handle Problem Language Result Execution time Memory
979367 2024-05-10T17:50:37 Z bachhoangxuan Towns (IOI15_towns) C++17
100 / 100
 16 ms 1072 KB 
#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=115;
#define pii pair<int,int>
#define fi first
#define se second

int d[maxn][maxn],b[maxn];

int get(int u,int v){
    if(u==v) return 0;
    if(d[u][v]) return d[u][v];
    return d[u][v]=d[v][u]=getDistance(u,v);
}

int hubDistance(int N, int sub) {
    memset(d,0,sizeof(d));
	pii a={0,0};
    for(int i=0;i<N;i++) a=max(a,{get(0,i),i});
    int D=0,R=1e6;
    for(int i=0;i<N;i++) D=max(D,get(a.se,i));
    map<int,vector<int>> mp;
    for(int i=0;i<N;i++){
        b[i]=(get(a.se,i)+get(0,i)-get(a.se,0))/2;
        int k=get(a.se,i)-b[i];
        mp[k].push_back(i);
        R=min(R,max(k,D-k));
    }
    int sl=0,sr=N;
    for(auto [k,x]:mp){
        sr-=(int)x.size();
        if(max(k,D-k)==R && sl<=N/2 && sr<=N/2){
            //cout << a.se << ' ' << k << '\n';
            vector<vector<int>> u,v;
            for(int i:x){
                if(!u.empty() && (int)u.back().size()>(int)v.back().size()){
                    if(get(u.back()[0],i)<b[u.back()[0]]+b[i]) u.back().push_back(i);
                    else v.back().push_back(i);
                }
                else{
                    u.push_back({i});
                    v.push_back({});
                }
            }
            int S=(int)u.back().size();
            for(int i=0;i<(int)u.size()-1;i++){
                if(get(u[i][0],u.back()[0])<b[u[i][0]]+b[u.back()[0]]) S+=(int)u[i].size();
                else{
                    for(int j:v[i]) if(get(j,u.back()[0])<b[j]+b[u.back()[0]]) S++;
                }
            }
            //cout << S << '\n';
            if(S<=N/2) R=-R;
        }
        sl+=(int)x.size();
    }

	return -R;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:17:28: warning: unused parameter 'sub' [-Wunused-parameter]
   17 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 348 KB Output is correct
2 Correct 9 ms 996 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 12 ms 860 KB Output is correct
5 Correct 13 ms 1068 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 348 KB Output is correct
2 Correct 9 ms 996 KB Output is correct
3 Correct 12 ms 1036 KB Output is correct
4 Correct 12 ms 1012 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 348 KB Output is correct
2 Correct 16 ms 1032 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 15 ms 860 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 540 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 14 ms 1032 KB Output is correct
3 Correct 12 ms 856 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 348 KB Output is correct
2 Correct 14 ms 1072 KB Output is correct
3 Correct 14 ms 860 KB Output is correct