oj.uz

Submission #297173

# Submission time Handle Problem Language Result Execution time Memory
297173 2020-09-11T10:22:17 Z peti1234 Towns (IOI15_towns) C++17
100 / 100
 23 ms 512 KB 
#include <bits/stdc++.h>
#include "towns.h"
using namespace std;
const int c=112;
int dist[c][c], a, b, h, n, mini, c1, c2, ks, kcs, ncs, ns, ert, ker, db[c];
bool jo, v[c];
vector<int> kis, k1, k2, nagy;
int tav(int a, int b) {
    if (a==b) return 0;
    if (!dist[a][b]) dist[a][b]=getDistance(a, b), dist[b][a]=dist[a][b];
    return dist[a][b];
}
int tavol(int x) {
    int pos=0;
    for (int i=0; i<n; i++) {
        int p=tav(x, i);
        if (p>tav(x,pos)) pos=i;
    }
    return pos;
}
bool ask(int b, int c) {
    int x=tav(a, b), y=tav(a, c), z=tav(b, c), p=(x+y-z)/2;
    return p>ker;
}
bool oszt(vector<int> sz) {
    int si=sz.size(), ki=-1, sum=0;
    for (int i=0; i<si; i++) db[i]=1, v[i]=0;
    for (int po=1; po<si; po*=2) {
        int a=-1, b=-1;
        for (int i=0; i<si; i++) {
            if (!v[i] && db[i]==po) {
                a=i;
                for (int j=i+1; j<si; j++) if (!v[j] && db[j]==po) {
                    b=j;
                    if (ask(sz[a], sz[b])) v[b]=1, db[a]+=db[b], db[b]=0;
                    else v[a]=1, v[b]=1;
                    a=-1, b=-1;
                    break;
                }
                if (a!=-1) ki=a;
            }
        }
    }
    if (ki!=-1) for (int i=0; i<si; i++) if (db[i]) sum+=ask(sz[ki], sz[i])*db[i];
    return sum<ert;
}
int hubDistance(int q, int w) {
    n=q, ert=n/2+1, jo=0, kis.clear(), k1.clear(), k2.clear(), nagy.clear();
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) dist[i][j]=0;
    a=tavol(0), b=tavol(a), h=tav(a, b), mini=h;
    for (int i=0; i<n; i++) {
        int x=tav(a, 0), y=tav(a, i), z=tav(i, 0), p=(x+y-z)/2;
        mini=min(mini, max(p, h-p));
    }
    c1=h-mini, c2=mini;
    for (int i=0; i<n; i++) {
        int x=tav(a, 0), y=tav(a, i), z=tav(i, 0), p=(x+y-z)/2;
        if (p<c1) kis.push_back(i);
        else if (p==c1) k1.push_back(i);
        else if (p==c2) k2.push_back(i);
        else nagy.push_back(i);
    }
    ks=kis.size(), kcs=k1.size(), ncs=k2.size(), ns=nagy.size();
    if (ks<ert && ncs+ns<ert) ker=c1, jo=oszt(k1);
    else if (ks+kcs<ert && ns<ert) ker=c2, jo=oszt(k2);
    if (!jo) mini*=-1;
    return mini;
}

Compilation message

towns.cpp: In function 'int tav(int, int)':
towns.cpp:8:21: warning: declaration of 'b' shadows a global declaration [-Wshadow]
    8 | int tav(int a, int b) {
      |                     ^
towns.cpp:5:20: note: shadowed declaration is here
    5 | int dist[c][c], a, b, h, n, mini, c1, c2, ks, kcs, ncs, ns, ert, ker, db[c];
      |                    ^
towns.cpp:8:21: warning: declaration of 'a' shadows a global declaration [-Wshadow]
    8 | int tav(int a, int b) {
      |                     ^
towns.cpp:5:17: note: shadowed declaration is here
    5 | int dist[c][c], a, b, h, n, mini, c1, c2, ks, kcs, ncs, ns, ert, ker, db[c];
      |                 ^
towns.cpp: In function 'bool ask(int, int)':
towns.cpp:21:22: warning: declaration of 'c' shadows a global declaration [-Wshadow]
   21 | bool ask(int b, int c) {
      |                      ^
towns.cpp:4:11: note: shadowed declaration is here
    4 | const int c=112;
      |           ^
towns.cpp:21:22: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   21 | bool ask(int b, int c) {
      |                      ^
towns.cpp:5:20: note: shadowed declaration is here
    5 | int dist[c][c], a, b, h, n, mini, c1, c2, ks, kcs, ncs, ns, ert, ker, db[c];
      |                    ^
towns.cpp: In function 'bool oszt(std::vector<int>)':
towns.cpp:26:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   26 |     int si=sz.size(), ki=-1, sum=0;
      |            ~~~~~~~^~
towns.cpp:29:13: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   29 |         int a=-1, b=-1;
      |             ^
towns.cpp:5:17: note: shadowed declaration is here
    5 | int dist[c][c], a, b, h, n, mini, c1, c2, ks, kcs, ncs, ns, ert, ker, db[c];
      |                 ^
towns.cpp:29:19: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   29 |         int a=-1, b=-1;
      |                   ^
towns.cpp:5:20: note: shadowed declaration is here
    5 | int dist[c][c], a, b, h, n, mini, c1, c2, ks, kcs, ncs, ns, ert, ker, db[c];
      |                    ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:63:16: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   63 |     ks=kis.size(), kcs=k1.size(), ncs=k2.size(), ns=nagy.size();
      |        ~~~~~~~~^~
towns.cpp:63:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   63 |     ks=kis.size(), kcs=k1.size(), ncs=k2.size(), ns=nagy.size();
      |                        ~~~~~~~^~
towns.cpp:63:46: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   63 |     ks=kis.size(), kcs=k1.size(), ncs=k2.size(), ns=nagy.size();
      |                                       ~~~~~~~^~
towns.cpp:63:62: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   63 |     ks=kis.size(), kcs=k1.size(), ncs=k2.size(), ns=nagy.size();
      |                                                     ~~~~~~~~~^~
towns.cpp:47:28: warning: unused parameter 'w' [-Wunused-parameter]
   47 | int hubDistance(int q, int w) {
      |                        ~~~~^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 384 KB Output is correct
2 Correct 16 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 21 ms 384 KB Output is correct
5 Correct 21 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 384 KB Output is correct
2 Correct 16 ms 384 KB Output is correct
3 Correct 21 ms 384 KB Output is correct
4 Correct 21 ms 512 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 384 KB Output is correct
2 Correct 21 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 21 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 384 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 384 KB Output is correct
2 Correct 23 ms 384 KB Output is correct
3 Correct 21 ms 384 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 384 KB Output is correct
2 Correct 21 ms 384 KB Output is correct
3 Correct 21 ms 384 KB Output is correct