Submission #297153

#	Time	Username	Problem	Language	Result	Execution time	Memory
297153		peti1234	Towns (IOI15_towns)	C++17	25 / 100	24 ms	896 KiB

towns

#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 getDistance(int a, int b) {
    cout << a << " " << b << "\n";
    int x; cin >> x;
    return x;
}
*/
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;
    //cout << "oszt " << si << "\n";
    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 (i==2) cout << "baj " << v[i] << " " << db[i] << "\n";
            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;
                        //cout << "ujsor\n";
                    } else {
                        v[a]=1, v[b]=1;
                    }
                    a=-1, b=-1;
                    break;
                }
                if (a!=-1) ki=a;
                //cout << po << " " << ki << endl;
            }
        }
    }
    //cout << "vege " << ki << endl;
    if (ki!=-1) {
        for (int i=0; i<si; i++) {
            if (db[i]) {
                sum+=ask(sz[ki], sz[i])*db[i];
            }
        }
    }
    //cout << "valasz " << sum << " " << ert << endl;
    return sum<ert;
}
int hubDistance(int q, int w) {
    n=q, ert=(n+1)/2, 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;
        //cout << "lehet " << i << " " << x << " " << y << " " << z << " " << p << "\n";
        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 (stderr)

towns.cpp: In function 'int tav(int, int)':
towns.cpp:15:21: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   15 | 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:15:21: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   15 | 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:28:22: warning: declaration of 'c' shadows a global declaration [-Wshadow]
   28 | bool ask(int b, int c) {
      |                      ^
towns.cpp:4:11: note: shadowed declaration is here
    4 | const int c=112;
      |           ^
towns.cpp:28:22: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   28 | 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:34:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   34 |     int si=sz.size(), ki=-1, sum=0;
      |            ~~~~~~~^~
towns.cpp:38:13: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   38 |         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:38:19: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   38 |         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:87:16: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   87 |     ks=kis.size(), kcs=k1.size(), ncs=k2.size(), ns=nagy.size();
      |        ~~~~~~~~^~
towns.cpp:87:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   87 |     ks=kis.size(), kcs=k1.size(), ncs=k2.size(), ns=nagy.size();
      |                        ~~~~~~~^~
towns.cpp:87:46: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   87 |     ks=kis.size(), kcs=k1.size(), ncs=k2.size(), ns=nagy.size();
      |                                       ~~~~~~~^~
towns.cpp:87:62: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   87 |     ks=kis.size(), kcs=k1.size(), ncs=k2.size(), ns=nagy.size();
      |                                                     ~~~~~~~~~^~
towns.cpp:70:28: warning: unused parameter 'w' [-Wunused-parameter]
   70 | int hubDistance(int q, int w) {
      |                        ~~~~^

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39