제출 #71673

#제출 시각아이디문제언어결과실행 시간메모리
71673mr_banana도시들 (IOI15_towns)C++17
35 / 100
28 ms5724 KiB
#include <bits/stdc++.h> #include "towns.h" using namespace std; const int MN=200,inf=1e9; int dist[MN][MN]; bool mark[MN][MN]; map<int,int> cnt; map<int,vector<int> > v1; int n; int getdists(int x){ int mi=0; for(int i=0;i<n;i++){ if(x!=i && !mark[x][i]){ dist[x][i]=dist[i][x]=getDistance(x,i); mark[x][i]=mark[i][x]=1; } if(dist[x][i]>dist[x][mi]){ mi=i; } } return mi; } int hubDistance(int N, int sub) { cnt.clear(); v1.clear(); memset(mark,0,sizeof mark); memset(dist,0,sizeof dist); n=N; int u=getdists(0); int v=getdists(u); getdists(v); int ans=inf; for(int i=0;i<n;i++){ int d=(dist[i][v]+dist[i][u]-dist[u][v])/2; cnt[dist[i][v]-d]++; v1[dist[i][v]-d].push_back(i); ans=min(ans,max(dist[i][v],dist[i][u])-d); } int n1=0,n2=n; bool f=0; if(sub==4){ for(auto i:cnt){ n2-=i.second; if(max(i.first,dist[u][v]-i.first)==ans && n1<=n/2 && n2<=n/2 && i.second<=n/2){ f=1; } n1+=i.second; } } if(sub==3){ for(int i=0;i<n;i++){ getdists(i); } for(auto i:v1){ n2-=i.second.size(); bool f1=1; if(max(i.first,dist[u][v]-i.first)){ for(int j:i.second){ int d1=(dist[v][j]+dist[u][j]-dist[u][v])/2; int cnt1=0; for(int k:i.second){ int d2=(dist[u][k]+dist[v][k]-dist[u][v])/2; if(dist[j][k]!=d1+d2){ cnt1++; } } if(cnt1>n/2){ f1=0; } } if(f1 && n1<=n/2 && n2<=n/2){ f=1; } } n1+=i.second.size(); } } if(!f && sub>2){ return -ans; } else{ return ans; } }

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:55:31: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
             n2-=i.second.size();
                               ^
towns.cpp:75:31: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
             n1+=i.second.size();
                               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...