oj.uz

Submission #542602

# Submission time Handle Problem Language Result Execution time Memory
542602 2022-03-27T05:09:17 Z tranxuanbach Towns (IOI15_towns) C++17
0 / 100
 1 ms 340 KB 
#ifndef FEXT

#include "towns.h"

#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

#ifdef FEXT

struct grader_t{
    static const int N = 110 + 5;

    int n;
    int dist[N][N];
} cac;

int getDistance(int i, int j){
    if (min(i, j) < 0 or max(i, j) >= cac.n){
        return 0;
    }
    return cac.dist[i][j];
}

#endif

namespace {
    const int N = 110 + 5;

    int dist[N][N];

    int getdist(int u, int v){
        if (u > v){
            swap(u, v);
        }
        if (dist[u][v] = -1){
            if (u == v){
                dist[u][v] = 0;
            }
            else{
                dist[u][v] = getDistance(u, v);
            }
        }
        return dist[u][v];
    }
}

int hubDistance(int n, int subtask){
    memset(dist, -1, sizeof(dist));
    // if (subtask == 1 or subtask == 2){
        int dia1 = 0, dia2 = 0;
        For(u, 1, n){
            if (getdist(0, u) > getdist(0, dia1)){
                dia1 = u;
            }
        }
        For(u, 1, n){
            if (getdist(dia1, u) > getdist(dia1, dia2)){
                dia2 = u;
            }
        }
        int dia = getdist(dia1, dia2);
        int ans = INT_MAX;
        For(u, 0, n){
            int d1 = getdist(u, dia1), d2 = getdist(u, dia2);
            int dd = (d1 + d2 - dia) / 2;
            d1 -= dd; d2 -= dd;
            ans = min(ans, max(d1, d2));
        }
        return ans;
    // }
    return 0;
}

#ifdef FEXT

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("KEK.inp", "r", stdin);
    freopen("KEK.out", "w", stdout);
int subtask, tests; cin >> subtask >> tests;
while (tests--){
    cin >> cac.n;
    For(i, 0, cac.n){
        For(j, 0, cac.n){
            cin >> cac.dist[i][j];
        }
    }
    cout << hubDistance(cac.n, subtask) << endl;
}
}

#endif

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Compilation message

towns.cpp: In function 'int {anonymous}::getdist(int, int)':
towns.cpp:57:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   57 |         if (dist[u][v] = -1){
      |             ~~~~~~~~~~~^~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:69:28: warning: unused parameter 'subtask' [-Wunused-parameter]
   69 | int hubDistance(int n, int subtask){
      |                        ~~~~^~~~~~~

Subtask #1
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 #2
0 / 12.0

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

Subtask #3
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 #4
0 / 10.0

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

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 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -