Submission #453552

#	Time	Username	Problem	Language	Result	Execution time	Memory
453552		PedroBigMan	Towns (IOI15_towns)	C++14	48 / 100	24 ms	728 KiB

towns

#include "towns.h"
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

vector<vector<ll> > gd;

ll getdistance(ll i,ll j)
{
	if(i==j) {gd[i][j]=0; return 0;}
	if(gd[i][j]!=0) {return gd[i][j];}
	gd[i][j]=getDistance(i,j); gd[j][i]=gd[i][j]; return gd[i][j];
}

class Graph
{
    public:
    ll N;
    vector<vector<ll> > adj; 
    vector<ll> visited; //for DFS/BFS
    vector<ll> current; //for CC
    
    Graph() {ll N=0LL;}
    
    Graph(vector<vector<ll> > ad)
    {
        adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false);}
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
        current.clear();
    }
    
    void DFS(ll s) 
    {
        if(visited[s]) {return;}
        visited[s]=true;
        current.pb(s); //only needed for CC
        REP(i,0,adj[s].size())
        {
            if(!visited[adj[s][i]]) {DFS(adj[s][i]);}
        }
        return;
    }
    
    vector<vector<ll> > CC()
    {
        Reset();
        ll fi=0; ll missing=N; REP(i,0,N) {visited[i]=false;}
        vector<vector<ll> > ans;
        while(missing>0)
        {
            REP(i,fi,N) {if(!visited[i]) {fi=i; break;}}
            current.clear();
            DFS(fi);
            ans.pb(current);
            missing-=current.size();
        }
        return ans;
    }
};

int hubDistance(int N, int sub) 
{
	ll D; gd.clear();
	vector<ll> xxxx; REP(i,0,N) {xxxx.pb(0);} REP(i,0,N) {gd.pb(xxxx);}
	vector<ll> d0; d0.pb(0); REP(i,1,N) {d0.pb(getdistance(0,i));}
	ll A = (ll) (max_element(whole(d0)) - d0.begin());
	vector<ll> d1,d2; 
	REP(i,0,N) {if(i==A) {d1.pb(0);} else {d1.pb(getdistance(A,i));}}
	ll B = (ll) (max_element(whole(d1)) - d1.begin());
	D = *max_element(whole(d1));
	REP(i,0,N) {if(i==B) {d2.pb(0);} else {d2.pb(getdistance(B,i));}}
	set<ll> s; 
	REP(i,0,N) {s.insert((d1[i]-d2[i]+D)/2LL);}
	unordered_map<ll,ll> m; set<ll>::iterator it =  s.begin(); ll ind=0LL; 
	ll R=D; vector<ll> poss_ind;
	while(it!=s.end()) 
	{
		R=min(R,max(*it,D-*it));
		m[*it]=ind; ind++; it++;
	}
	it=s.begin(); ind=0;
	while(it!=s.end())
	{
		if(max(*it,D-*it)==R) {poss_ind.pb(ind);}
		ind++; it++;
	}
	vector<pl> p; //pairs {diameter projection index, distance to projection}
	REP(i,0,N)
	{
		ll val1 = m[(d1[i]-d2[i]+D)/2LL]; 
		ll val2 = (d1[i]+d2[i]-D)/2LL;
		p.pb({val1,val2});
	}
	vector<ll> oc; REP(i,0,s.size()) {oc.pb(0LL);}
	REP(i,0,N) {oc[p[i].ff]++;}
	ll hub = poss_ind[0];
	ll S = s.size();
	ll sum1,sum2;
	if(poss_ind.size()==2)
	{
		sum1=0LL;sum2=0LL;
		REP(i,poss_ind[0]+1,S) {sum1+=oc[i];}
		REP(i,0,poss_ind[1]) {sum2+=oc[i];}
		if(2*sum1==N) {return R;}
		else if(2*sum1>N) {hub=poss_ind[1];}
	}
	sum1=0LL;sum2=0LL;
	REP(i,0,hub) {sum1+=oc[i];} REP(i,hub+1,S) {sum2+=oc[i];}
	if(2*sum1>N || 2*sum2>N) {return -R;}
	if(sub!=3) 
	{
		if(2*oc[hub]>N) {return -R;}
		else {return R;}
	}
	vector<ll> xx; vector<vector<ll> > adj; REP(i,0,N) {adj.pb(xx);}
	REP(i,0,N)
	{
		REP(j,0,i)
		{
			if(p[i].ff!=hub || p[j].ff!=hub) {continue;}
			if((p[i].ss+p[j].ss)!=getdistance(i,j)) {adj[i].pb(j); adj[j].pb(i);}
		}
	}
	Graph G(adj);
	vector<vector<ll> > CC = G.CC();
	REP(i,0,CC.size()) 
	{
		if(2*CC[i].size()>N) {return -R;}
	}
	return R;
}

Compilation message (stderr)

towns.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
towns.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
towns.cpp: In function 'll getdistance(ll, ll)':
towns.cpp:54:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   54 |  gd[i][j]=getDistance(i,j); gd[j][i]=gd[i][j]; return gd[i][j];
      |                       ^
towns.cpp:54:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   54 |  gd[i][j]=getDistance(i,j); gd[j][i]=gd[i][j]; return gd[i][j];
      |                         ^
towns.cpp: In constructor 'Graph::Graph()':
towns.cpp:65:17: warning: declaration of 'N' shadows a member of 'Graph' [-Wshadow]
   65 |     Graph() {ll N=0LL;}
      |                 ^
towns.cpp:60:8: note: shadowed declaration is here
   60 |     ll N;
      |        ^
towns.cpp:65:17: warning: unused variable 'N' [-Wunused-variable]
   65 |     Graph() {ll N=0LL;}
      |                 ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:150:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  150 |   if(2*sum1==N) {return R;}
      |                         ^
towns.cpp:155:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  155 |  if(2*sum1>N || 2*sum2>N) {return -R;}
      |                                   ^~
towns.cpp:158:27: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  158 |   if(2*oc[hub]>N) {return -R;}
      |                           ^~
towns.cpp:159:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  159 |   else {return R;}
      |                ^
towns.cpp:174:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  174 |   if(2*CC[i].size()>N) {return -R;}
      |      ~~~~~~~~~~~~~~^~
towns.cpp:174:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  174 |   if(2*CC[i].size()>N) {return -R;}
      |                                ^~
towns.cpp:176:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  176 |  return R;
      |         ^

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