oj.uz

Submission #235659

# Submission time Handle Problem Language Result Execution time Memory
235659 2020-05-29T08:13:47 Z ryansee Towns (IOI15_towns) C++14
49 / 100
 30 ms 1024 KB 
// I'm just asserting something
#include "towns.h"
#include <bits/stdc++.h>
 
using namespace std;
 
using ii = pair<int, int>;
 
#define X first
#define Y second
 
int v = 0, s, t, r;
int distv[120], dists[120], memo[120][120];
 
bool sameConn(int x1, int x2) {
    if(x1>x2) swap(x1,x2);
    if(~memo[x1][x2]) return memo[x1][x2];
	int x = getDistance(x1, x2);
	return memo[x1][x2] = (dists[x1] + dists[x2] - x > 2 * r);
}
 
int hubDistance(int N, int sub) {
    memset(memo, -1, sizeof memo);
	int maxv = 0;
	for(int i = 0 ; i < N ; i++) {
		distv[i] = getDistance(v, i);
		maxv = max(maxv, distv[i]);
	}
	
	for(int i = 0 ; i < N ; i++)
		if(distv[i] == maxv)
			s = i;
			
	int dsv = maxv;
			
	maxv = 0;
	for(int i = 0 ; i < N ; i++) {
		dists[i] = getDistance(s, i);
		maxv = max(maxv, dists[i]);
	}
	
	int d = maxv;
	
	for(int i = 0 ; i < N ; i++)
		if(dists[i] == maxv)
			t = i;	
 
	int res = 1e9;
	vector<int> poss;
	for(int i = 0 ; i < N ; i++) {
		int a = (dists[i] + dsv - distv[i]) / 2;
		int b = dsv - a;
		if(max({a, d - a}) < res) {
			res = max({a, d - a});
			poss.clear();
			poss.push_back(a);
		} else if(max({a, d - a}) == res)
			poss.push_back(a);
		//~ cout << i << " " << res << endl;
	}
	
	vector<int> B;
	for(int i = 0 ; i < N ; i++)
		B.push_back((dists[i] + dsv - distv[i]) / 2);
		
	sort(B.begin(), B.end());
	
	int m;
	if(B.size() % 2 == 0) {
		int m1 = B[B.size() / 2 - 1];
		int m2 = B[B.size() / 2];
		if(m1 == m2)
			m = m1;
		else {
			if(find(poss.begin(), poss.end(), m1) == poss.end()
				&& find(poss.begin(), poss.end(), m2) == poss.end()) {
				//~ cout << "aa" << endl;
				return -res;
			}		
			return res;
		}
	} else
		m = B[B.size() / 2];
		
	if(find(poss.begin(), poss.end(), m) == poss.end()) {
		//~ cout << "aa" << endl;
		return -res;
	}
	r = m;
		
	vector<int> list, bucket;
	for(int i = 0 ; i < N ; i++) {
		if((dists[i] + dsv - distv[i]) / 2 == m) {
			if(list.empty() || !sameConn(i, list.back())) {
				list.push_back(i);
				if(!bucket.empty()) {
					list.push_back(bucket.back());
					bucket.pop_back();
				}
			} else
				bucket.push_back(i);
		}
      	for(int i=1;i<bucket.size();++i) assert(sameConn(bucket[i-1], bucket[i]));
	}
		
	int T = list.back();
		
	int cnt = 0;
	while(!list.empty()) {
		if(sameConn(list.back(), T)) {
			cnt++;
			if(list.size() > 1) {
				list.pop_back();
				list.pop_back();
			} else {
				bucket.push_back(list.back());
				list.pop_back();
			}
		} else {
			list.pop_back();
			if(bucket.empty()) {
				//~ cout << "D" << endl;
				return res;
			}
			bucket.pop_back();
			cnt++;
		}
	}
	
	cnt += bucket.size();
	
	if(cnt <= N / 2) {
		//~ cout << "c" << endl;
		return res;
	}
	//~ cout << "ab" << endl;
	return -res;
}

Compilation message

towns.cpp: In function 'bool sameConn(int, int)':
towns.cpp:19:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  return memo[x1][x2] = (dists[x1] + dists[x2] - x > 2 * r);
         ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:52:7: warning: unused variable 'b' [-Wunused-variable]
   int b = dsv - a;
       ^
towns.cpp:103:16: warning: declaration of 'i' shadows a previous local [-Wshadow]
        for(int i=1;i<bucket.size();++i) assert(sameConn(bucket[i-1], bucket[i]));
                ^
towns.cpp:92:10: note: shadowed declaration is here
  for(int i = 0 ; i < N ; i++) {
          ^
towns.cpp:103:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int i=1;i<bucket.size();++i) assert(sameConn(bucket[i-1], bucket[i]));
                    ~^~~~~~~~~~~~~~
towns.cpp:130:21: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  cnt += bucket.size();
                     ^
towns.cpp:22:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub) {
                            ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 384 KB Output is correct
2 Correct 22 ms 896 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 28 ms 896 KB Output is correct
5 Correct 27 ms 896 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 512 KB Output is correct
2 Correct 28 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 28 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 384 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 384 KB Output is correct
2 Correct 27 ms 896 KB Output is correct
3 Correct 30 ms 1024 KB Output is correct

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -