oj.uz

Submission #876600

# Submission time Handle Problem Language Result Execution time Memory
876600 2023-11-22T04:48:07 Z HuyQuang_re_Zero Towns (IOI15_towns) C++14
100 / 100
 14 ms 1412 KB 
#include <bits/stdc++.h>
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
using namespace std;
#include "towns.h"
/*
struct Interactive
{
    int n,u,v,dis[202][202];
    void Init()
    {
        cin>>n;
        for(u=0;u<n;u++)
            for(v=0;v<n;v++) cin>>dis[u][v];
    }
} IR;
int getDistance(int u,int v)
{
    cout<<u<<" "<<v<<'\n';
    return IR.dis[u][v];
}
*/

int n,d[202][202],u,v,to_x[202],to_y[202];
vector <int> node[202];
int dis(int u,int v)
{
    if(u==v) return 0;
    if(u>v) swap(u,v);
    if(d[u][v]>-1) return d[u][v];
    return d[u][v]=getDistance(u,v);
}
int hubDistance(int n,int sub)
{
    memset(d,-1,sizeof(d));
    int x=-1,y=-1;
    for(u=1;u<n;u++)
        if(x==-1 || dis(0,x)<dis(0,u)) x=u;
    for(u=0;u<n;u++)
        if(y==-1 || dis(x,y)<dis(x,u)) y=u;



    int mx_path=dis(x,y),res=1e9;
    for(u=0;u<n;u++)
    {
        to_x[u]=(dis(u,x)+dis(0,x)-dis(0,u))/2;
        to_y[u]=mx_path-to_x[u];
        res=min(res,max(to_x[u],to_y[u]));
    }
    int okx=0,oky=0,nearx=0,neary=0;
    vector <int> to_center,alive,dead;
    for(u=0;u<n;u++)
    {
        if(max(to_x[u],to_y[u])==res)
        {
            okx|=(to_x[u]<=to_y[u]),oky|=(to_y[u]<to_x[u]);
            to_center.push_back(u);
        }
        nearx+=(to_x[u]<=to_y[u]);
        neary+=(to_y[u]<to_x[u]);
    }



    if(okx+oky==1)
    {
        alive=to_center;
        if(okx==1 && (nearx-alive.size()>n/2 || neary>n/2)) return -res;
        if(oky==1 && (neary-alive.size()>n/2 || nearx>n/2)) return -res;
    }
    else if(nearx==neary) return res;
    else if(nearx>neary)
    {
        for(u=0;u<n;u++)
            if(max(to_x[u],to_y[u])==res && (to_x[u]<=to_y[u]))
                alive.push_back(u);
        if(nearx-alive.size()>n/2) return -res;
    }
    else
    {
        for(u=0;u<n;u++)
            if(max(to_x[u],to_y[u])==res && (to_y[u]<to_x[u]))
                alive.push_back(u);
        if(neary-alive.size()>n/2) return -res;
    }


    for(u=0;u<n;u++) node[u].clear(),node[u].push_back(u);
    int last_odd=-1;
    while(alive.size()>0)
    {
        vector <int> vec;
        for(int i=0;i+1<alive.size();i+=2)
        {
            u=node[alive[i]][0];
            v=node[alive[i+1]][0];
            if(dis(x,u)+dis(x,v)-2*to_x[u]!=dis(u,v)) //Same part
            {
                vec.push_back(alive[i]);
                for(int k:node[alive[i+1]]) node[alive[i]].push_back(k);
            }
            else dead.push_back(alive[i]),dead.push_back(alive[i+1]);
        }
        if(alive.size()%2==1)
        {
            if(last_odd>-1) dead.push_back(last_odd);
            last_odd=alive.back();
        }
        alive=vec;
    }

    if(last_odd==-1) return res;
    u=last_odd;
    int cnt=node[u].size();
    for(int v:dead)
        if(dis(x,u)+dis(x,v)-2*to_x[u]!=dis(u,v)) cnt+=node[v].size();
    if(cnt<=n/2) return res;
    return -res;
}
/*
int main()
{
    freopen("towns.inp","r",stdin);
    freopen("towns.out","w",stdout);
    IR.Init();
    n=IR.n;
    cout<<hubDistance(n,0);
}
*/

Compilation message

towns.cpp: In function 'int dis(int, int)':
towns.cpp:37:19: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   37 | int dis(int u,int v)
      |               ~~~~^
towns.cpp:35:21: note: shadowed declaration is here
   35 | int n,d[202][202],u,v,to_x[202],to_y[202];
      |                     ^
towns.cpp:37:13: warning: declaration of 'u' shadows a global declaration [-Wshadow]
   37 | int dis(int u,int v)
      |         ~~~~^
towns.cpp:35:19: note: shadowed declaration is here
   35 | int n,d[202][202],u,v,to_x[202],to_y[202];
      |                   ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:44:21: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   44 | int hubDistance(int n,int sub)
      |                 ~~~~^
towns.cpp:35:5: note: shadowed declaration is here
   35 | int n,d[202][202],u,v,to_x[202],to_y[202];
      |     ^
towns.cpp:80:41: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |         if(okx==1 && (nearx-alive.size()>n/2 || neary>n/2)) return -res;
      |                       ~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:81:41: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |         if(oky==1 && (neary-alive.size()>n/2 || nearx>n/2)) return -res;
      |                       ~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:89:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         if(nearx-alive.size()>n/2) return -res;
      |            ~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:96:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |         if(neary-alive.size()>n/2) return -res;
      |            ~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:105:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int i=0;i+1<alive.size();i+=2)
      |                     ~~~^~~~~~~~~~~~~
towns.cpp:126:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  126 |     int cnt=node[u].size();
      |             ~~~~~~~~~~~~^~
towns.cpp:127:13: warning: declaration of 'v' shadows a global declaration [-Wshadow]
  127 |     for(int v:dead)
      |             ^
towns.cpp:35:21: note: shadowed declaration is here
   35 | int n,d[202][202],u,v,to_x[202],to_y[202];
      |                     ^
towns.cpp:128:69: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  128 |         if(dis(x,u)+dis(x,v)-2*to_x[u]!=dis(u,v)) cnt+=node[v].size();
      |                                                                     ^
towns.cpp:44:27: warning: unused parameter 'sub' [-Wunused-parameter]
   44 | int hubDistance(int n,int sub)
      |                       ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1372 KB Output is correct
2 Correct 9 ms 860 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 12 ms 1116 KB Output is correct
5 Correct 12 ms 1116 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1112 KB Output is correct
2 Correct 9 ms 1116 KB Output is correct
3 Correct 12 ms 1020 KB Output is correct
4 Correct 12 ms 1024 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1412 KB Output is correct
2 Correct 14 ms 1116 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 12 ms 1132 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 860 KB Output is correct
2 Correct 12 ms 1116 KB Output is correct
3 Correct 12 ms 1116 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1112 KB Output is correct
2 Correct 12 ms 1116 KB Output is correct
3 Correct 12 ms 1116 KB Output is correct