Submission #134724

#	Time	Username	Problem	Language	Result	Execution time	Memory
134724		nvmdava	Towns (IOI15_towns)	C++17	25 / 100	21 ms	892 KiB

towns

    #include "towns.h"
    #include <bits/stdc++.h>
    using namespace std;
     
    int dv[200], du[200];
    map<int, std::vector<int>> dis;
     
    int hubDistance(int N, int sub) {
    	int v = 0, u = 0;
    	for(int i = 0; i < N; i++)
    		dv[i] = getDistance(v, i);
    	for(int i = 0; i < N; i++)
    		if(dv[i] > dv[u])
    			u = i;
    	int D = dv[u], T = 0;
    	for(int i = 0; i < N; i++){
    		du[i] = getDistance(u, i);
    		T = max(T, du[i]);
    	}
    	swap(v, u);
    	swap(dv, du);
    	int r = 1000000000;
    	for(int i = 0; i < N; i++){
    		int q = (D + dv[i] - du[i]) >> 1;
    		r = min(r, max(q, T - q));
    	}
      return r;
    	for(int i = 0; i < N; i++)
    		dis[D + dv[i] - du[i]].push_back(i);
    	int chk;
    	if(dis.find(r * 2) != dis.end())
    		chk = r * 2;
    	else
    		chk = (T - r) * 2;
    	int c1 = 0, c2 = 0, c3 = 0;
    	for(int i = 0; i < N; i++){
    		if(D + dv[i] - du[i] < 2 * r) c1++;
    		else if(D + dv[i] - du[i] > 2 * r) c2++;
    		else c3++;
    	}
    	if(max(c1, max(c2, c3)) <= N / 2) return r;
    	if(c1 > N / 2) return -r;
    	if(c2 > N / 2){
    		if(chk == r * 2 && dis.find((T - r) * 2) != dis.end()) chk = (T - r) * 2;
    		else return -r;
    	}
    	return r;
     
    	vector<int> fer = dis[chk];
    	vector<int> rep;
    	int i;
    	for(i = 1; i < fer.size(); i++){
    		if(getDistance(fer[i], fer[i - 1]) == dv[fer[i]] + du[fer[i - 1]] - D){
    			rep.push_back(i - 1);
    			rep.push_back(i);
    			i++;
    		}
     
    	}
    	if(i == fer.size() + 1) return r;
    	int sz = fer.size() - rep.back() - 1, l = 0;
    	for(int& x : rep){
    		if(getDistance(fer[x], fer.back()) != dv[fer[x]] + du[fer.back()] - D){
    			sz += x - l;
    		}
    		l = x;
    	}
    	if(sz > N / 2) return -r;
    	return r;
    }

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(i = 1; i < fer.size(); i++){
                 ~~^~~~~~~~~~~~
towns.cpp:60:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(i == fer.size() + 1) return r;
         ~~^~~~~~~~~~~~~~~~~
towns.cpp:61:39: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
      int sz = fer.size() - rep.back() - 1, l = 0;
               ~~~~~~~~~~~~~~~~~~~~~~~~^~~
towns.cpp:8:32: warning: unused parameter 'sub' [-Wunused-parameter]
     int hubDistance(int N, int sub) {
                                ^~~

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