| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 453552 |
2021-08-04T12:19:49 Z |
PedroBigMan |
Towns (IOI15_towns) |
C++14 |
|
24 ms |
728 KB |
#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
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;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
332 KB |
Output is correct |
| 2 |
Correct |
15 ms |
444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
21 ms |
428 KB |
Output is correct |
| 5 |
Correct |
20 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
332 KB |
Output is correct |
| 2 |
Correct |
19 ms |
716 KB |
Output is correct |
| 3 |
Correct |
20 ms |
728 KB |
Output is correct |
| 4 |
Correct |
24 ms |
716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
588 KB |
Output is correct |
| 2 |
Correct |
23 ms |
568 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
23 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
