oj.uz

Submission #1065891

# Submission time Handle Problem Language Result Execution time Memory
1065891 2024-08-19T12:37:51 Z anango Towns (IOI15_towns) C++17
0 / 100
 12 ms 600 KB 
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

int INF = 1LL<<60;
int n;

map<pair<int,int>,int> cache;

int getdist(int u, int v) {
    if (u==v) {
        return 0;
    }
    if (u>v) swap(u,v);
    if (cache.count({u,v})) {
        return cache[{u,v}];
    }
    return cache[{u,v}] = getDistance(u,v);
}

signed hubDistance(signed N, signed sub) {
    if (sub<=2) {
        n=N;
        
        vector<int> dist0(n);
        for (int i=0; i<n; i++) {
            dist0[i] = getdist(0,i);
        }
        vector<int> cities(n); iota(cities.begin(), cities.end(), (int)0);
        vector<int> sortedbyd0(cities.begin(), cities.end());
        sort(sortedbyd0.begin(), sortedbyd0.end(), [&](const int i1, const int i2) {
            return dist0[i1]<dist0[i2];
        });
        int u = sortedbyd0.back();
        vector<int> distu(n);
        for (int i=0; i<n; i++) {
            distu[i] = getdist(u,i);
        }
        
        //2n-3 used
        vector<int> sortedbydu(cities.begin(), cities.end());
        sort(sortedbydu.begin(), sortedbydu.end(), [&](const int i1, const int i2) {
            return distu[i1]<distu[i2];
        });
        int v = sortedbydu.back();
        //u-v is a diameter
        int length = distu[v];
        int mindiff = INF;
        for (int i=0; i<n; i++) {
            mindiff = min(mindiff,abs(getdist(i,u)-getdist(i,v)));
        }
        assert(length%2==mindiff%2);
        return (length+mindiff)/2;
    }
    else {
        return 0;
    }

}

Compilation message

towns.cpp: In function 'long long int getdist(long long int, long long int)':
towns.cpp:19:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   19 |     return cache[{u,v}] = getDistance(u,v);
      |                                       ^
towns.cpp:19:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   19 |     return cache[{u,v}] = getDistance(u,v);
      |                                         ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:54:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   54 |         return (length+mindiff)/2;
      |                ~~~~~~~~~~~~~~~~^~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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