제출 #1096772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1096772		MMihalev	도시들 (IOI15_towns)	C++17	35 / 100	11 ms	1116 KiB

towns

#include "towns.h"
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<cmath>
using namespace std;
const int MAX_N=2e2+2;
int diam;
int tov[MAX_N];
int tou[MAX_N];
int to0[MAX_N];
int ma[MAX_N][MAX_N];
set<int>nodes,nodes1,nodes2;
int n;
int u,v;
int q;
bool check(int a,int b)
{
    int dd;
    if(a>b)swap(a,b);
    if(ma[a][b])dd=ma[a][b];
    else
    {
        if(q==(n*(n-1))/2)while(1);
        dd=getDistance(a,b);
        ma[a][b]=dd;
        q++;
    }

    if(tou[a]+tov[b]-diam==dd)return 0;
    return 1;
}
int hubDistance(int N, int sub)
{
    q=0;
    nodes1.clear();
    nodes2.clear();
    n=N;
    for(int i=0;i<n;i++)
    {
        to0[i]=0;
        tou[i]=0;
        tov[i]=0;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            ma[i][j]=0;
        }
    }

    u=0;
    int far=0;
    for(int i=1;i<n;i++)
    {
        int cur=getDistance(u,i);
        ma[0][i]=cur;
        q++;

        to0[i]=cur;
        if(cur>far)
        {
            far=cur;
            v=i;
        }
    }//0->v

    diam=0;
    for(int i=0;i<n;i++)
    {
        if(i==v)continue;
        int cur;
        if(i==0)cur=to0[v];
        else
        {
            q++;
            cur=getDistance(i,v);
            ma[min(i,v)][max(i,v)]=cur;
        }

        tov[i]=cur;

        if(cur>diam)
        {
            diam=cur;
            u=i;
        }
    }//v->u

    for(int i=0;i<n;i++)
    {
        if(i==u)continue;
        if(i==0){tou[i]=to0[u];continue;}
        if(i==v){tou[i]=tov[u];continue;}

        if(u!=0)
        {
            q++;
            tou[i]=getDistance(u,i);
            ma[min(i,u)][max(i,u)]=tou[i];
        }
        else tou[i]=to0[i];
    }//u->all


    int cntneg=1,cntpos=1,cntbaseneg=0,cntbasepos=0;
    int mindif=1e9;

    for(int i=0;i<n;i++)
    {
        if(i==u or i==v)continue;

        int x=tou[i];
        int y=tov[i];
        int com=((x+y)-diam)/2;

        x-=com;
        y-=com;

        int res=x-y;

        mindif=min(mindif,abs(res));
    }

    for(int i=0;i<n;i++)
    {
        if(i==u or i==v)continue;

        int x=tou[i];
        int y=tov[i];
        int com=((x+y)-diam)/2;

        x-=com;
        y-=com;

        int res=x-y;

        if(abs(res)==mindif)
        {
            if(res<=0){cntbaseneg++;nodes1.insert(i);}
            else {cntbasepos++;nodes2.insert(i);}
        }
        else if(res<0)cntneg++;
        else cntpos++;
    }

    int R=(diam-mindif)/2+mindif;

    if(sub==4 or sub<=2)
    {
        if(cntbaseneg*cntbasepos!=0)
        {
            if(cntneg*2>n or (cntbasepos+cntpos)*2>n or cntbaseneg*2>n)return -R;
            if(cntpos*2>n or (cntbaseneg+cntneg)*2>n or cntbasepos*2>n)return -R;
            return R;
        }
        else
        {
            if(cntneg*2>n or cntpos*2>n or (cntbaseneg+cntbasepos)*2>n)return -R;
            return R;
        }
    }

    if(cntneg*2>n or cntpos*2>n)return -R;

    if(cntbasepos*2<=n && cntbaseneg*2<=n)return R;

    if(cntbaseneg*2>n)nodes=nodes1;
    else nodes=nodes2;

    set<int>NO=nodes;

    int overhalf=0;
    int other=0;

    while(nodes.size())
    {
        if(nodes.size()==2)
        {
            overhalf=(*(nodes.begin()));
            nodes.erase(overhalf);
            other=(*(nodes.begin()));
            break;
        }
        if(nodes.size()==1){overhalf=(*(nodes.begin()));break;}
        vector<int>nod;
        set<int>nnodes;
        for(int x:nodes)nod.push_back(x);
        for(int i=1;i<nod.size();i+=2)
        {
            if(check(nod[i],nod[i-1]))nnodes.insert(nod[i]);
        }
        if((nod.size())%2==1)
        {
            int sz=nod.size();
            nnodes.insert(nod[sz-1]);
        }
        nodes=nnodes;
    }

    if(overhalf==0)return R;

    int cnt=1;
    for(int i:NO)
    {
        if(i==overhalf)continue;
        if(check(i,overhalf))cnt++;
    }

    if(2*cnt>n)R=-R;

    cnt=1;
    overhalf=other;
    for(int i:NO)
    {
        if(i==overhalf)continue;
        if(check(i,overhalf))cnt++;
    }

    if(2*cnt>n)R=-R;

	return R;
}

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:191:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |         for(int i=1;i<nod.size();i+=2)
      |                     ~^~~~~~~~~~~
towns.cpp:197:28: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  197 |             int sz=nod.size();
      |                    ~~~~~~~~^~

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