Submission #257603

#	Time	Username	Problem	Language	Result	Execution time	Memory
257603		davi_bart	Dreaming (IOI13_dreaming)	C++14	100 / 100	240 ms	11116 KiB

dreaming

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pair<int,int> > v[100010];
vector<pair<int,int> >group;
vector<bool> vis(100010,0);
vector<int> distA(100010,0),distB(100010,0);//profondita;

void dist(int pos){
  priority_queue<pair<pair<int,int>,int>,vector<pair<pair<int,int>,int > >,greater<pair<pair<int,int>,int> > >q;
  q.push({{0,pos},-1});
  vector<int> y;
  int A=pos;
  while(!q.empty()){
    int p=q.top().first.second;
    int d=q.top().first.first;
    int prec=q.top().second;
    q.pop();
    y.push_back(p);
    vis[p]=1;
    A=p;
    for(auto x:v[p])if(x.first!=prec)q.push({{d+x.second,x.first},p});
  }
  q.push({{0,A},-1});
  int B=A;
  while(!q.empty()){
    int p=q.top().first.second;
    int d=q.top().first.first;
    int prec=q.top().second;
    q.pop();
    B=p;
    distA[p]=d;
    for(auto x:v[p])if(x.first!=prec)q.push({{d+x.second,x.first},p});
  }
  q.push({{0,B},-1});
  while(!q.empty()){
    int p=q.top().first.second;
    int d=q.top().first.first;
    int prec=q.top().second;
    q.pop();
    distB[p]=d;
    for(auto x:v[p])if(x.first!=prec)q.push({{d+x.second,x.first},p});
  }
  int mi=1e9;
  int best;
  for(int x:y){
    if(max(distA[x],distB[x])<mi){
      mi=max(distA[x],distB[x]);
      best=x;
    }
  }
  group.push_back({mi,best});
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
  for(int i=0;i<M;i++){
    v[A[i]].push_back({B[i],T[i]});
    v[B[i]].push_back({A[i],T[i]});
  }
  for(int i=0;i<N;i++){
    if(vis[i]==0)dist(i);
  }
  sort(group.begin(),group.end(),greater<pair<int,int> >());
  for(int i=1;i<group.size();i++){
    int a=group[0].second;
    int b=group[i].second;
    v[a].push_back({b,L});
    v[b].push_back({a,L});
  }
  priority_queue<pair<pair<int,int>,int>,vector<pair<pair<int,int>,int > >,greater<pair<pair<int,int>,int> > >q;
  q.push({{0,0},-1});
  int f=0;
  while(!q.empty()){
    int p=q.top().first.second;
    int d=q.top().first.first;
    int prec=q.top().second;
    q.pop();
    f=p;
    for(auto x:v[p])if(x.first!=prec)q.push({{d+x.second,x.first},p});
  }
  q.push({{0,f},-1});
  int z=0;
  while(!q.empty()){
    int p=q.top().first.second;
    int d=q.top().first.first;
    int prec=q.top().second;
    q.pop();
    z=d;
    distA[p]=d;
    for(auto x:v[p])if(x.first!=prec)q.push({{d+x.second,x.first},p});
  }
  return z;
}
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3

*//*
#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)

#define MAX_N 100000

static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];

int main(){
	int N, M, L, i;
	int res;
	res = scanf("%d%d%d", &N, &M, &L);
	for (i = 0; i < M; i++)
		res = scanf("%d%d%d", &A[i], &B[i], &T[i]);

	int answer = travelTime(N, M, L, A, B, T);
	printf("%d\n", answer);

	return 0;
}*/

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:66:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<group.size();i++){
               ~^~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23