oj.uz

Submission #206060

# Submission time Handle Problem Language Result Execution time Memory
206060 2020-03-02T04:54:15 Z Segtree Towns (IOI15_towns) C++14
25 / 100
 46 ms 4344 KB 
#include"towns.h"
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x,begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod

#define X 1000010
int cnts[X];
int hubDistance(int N,int SUBTASK){
	int ma=0,A=-1;
	for(int i=0;i<N;i++){
		int res=getDistance(0,i);
		if(res>ma)ma=res,A=i;
	}
	int dista[110];
	ma=0;
	int B=-1;
	for(int i=0;i<N;i++){
		int res=getDistance(A,i);
		dista[i]=res;
		if(res>ma)ma=res,B=i;
	}
	int distb[110];
	for(int i=0;i<N;i++){
		int res=getDistance(B,i);
		distb[i]=res;
	}
	rep(i,X)cnts[i]=0;
	set<ll> S;
	int ab=dista[B];
	int ans=1e9;
	for(int i=0;i<N;i++){
		int ax=dista[i],bx=distb[i];
		int q=(ax+bx-ab)/2;
		int p=ax-q;
		int r=bx-q;
		chmin(ans,max(p,r));
		S.insert(p);
		cnts[p]++;
		//cout<<i<<":"<<ax<<" "<<bx<<" "<<p<<" "<<q<<" "<<r<<endl;
	}
	ll U,V=-1;
	ll rui=0;
	for(auto t:S){
		rui+=cnts[t];
		if(rui>N/2){
			U=t;
			break;
		}
	}
	rui=0;
	for(auto t:S){
		rui+=cnts[t];
		if(rui==N/2){
			V=t;
			break;
		}
	}
	bool th=0;
	if(ans==max(U,ab-U))th=1;
	if(ans==max(V,ab-V)&&V>=0)th=1;
	if(th==0)ans*=-1;
	return ans;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:18:27: warning: unused parameter 'SUBTASK' [-Wunused-parameter]
 int hubDistance(int N,int SUBTASK){
                           ^~~~~~~
towns.cpp:69:18: warning: 'U' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if(ans==max(U,ab-U))th=1;
                ~~^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4216 KB Output is correct
2 Correct 30 ms 4216 KB Output is correct
3 Correct 7 ms 4216 KB Output is correct
4 Correct 35 ms 4344 KB Output is correct
5 Correct 38 ms 4344 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4216 KB Output is correct
2 Correct 33 ms 4216 KB Output is correct
3 Correct 35 ms 4216 KB Output is correct
4 Correct 36 ms 4216 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 4220 KB Output isn't correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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