Submission #245086

#	Time	Username	Problem	Language	Result	Execution time	Memory
245086		lakshith_	Dreaming (IOI13_dreaming)	C++14	100 / 100	161 ms	10868 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back

using namespace std;

int MAX_IN = 1e5;

vector<vector<pair<int,int>>> adjList(100000,vector<pair<int,int>>());
vector<pair<int,int>> centers;
int now = 0;
int dis[100000];
int parent[100000];
int visited[100000];
int dist=0;

void bfs(int node){
    now = node , dist = 0 ;
    queue< pair<int , pair<int , int> > >q ;
    q.push({node , {0 , -2}}) ;
    dis[node] = 0 ;
    parent[node] = node ;
    while(!q.empty())
    {
        pair<int , pair<int , int> >p = q.front() ;
        q.pop() ;
        int cur = p.first , d = p.second.first , par = p.second.second ;
        visited[cur] = 1 ;
        parent[cur] = par ;
        if(d > dist)
            now = cur , dist = d ;
        for(auto &child : adjList[cur])
        {
            if(child.first == par)
                continue;
            dis[child.first] = child.second ;
            q.push({child.first , {d + child.second , cur}}) ;
        }
    }
    return ;
}

int travelTime(int n,int m,int l,int a[],int b[],int t[]){
  memset(parent , -1 , sizeof(parent));
  for(int i=0;i<m;i++){
    adjList.at(a[i]).push_back({b[i],t[i]});
    adjList.at(b[i]).push_back({a[i],t[i]});
  }
  for(int i=0;i<n;i++){
    if(visited[i]==1)continue;
//     cout << i << "\n";
    //find the farthest leaf
    bfs(i);
    bfs(now);
//     cout << dist << "\n";
    //only one node
    if(dist==0){centers.pb({0,i});continue;}
    //find the center of the component
    int sum = 0,cur = now,prv=-1;
    for(int j=0;j<n;j++){
      sum += dis[cur];
      prv = cur;
      cur = parent[cur];
      if(sum*2>=dist)break;
    }
    int a = max(sum,dist-sum);
    sum -= dis[prv] ;
    if(max(sum , dist - sum) < a && prv != -1)
        centers.pb({max(sum , dist - sum) , prv}) ;
    else
        centers.pb({a , cur}) ;
//     cout << a << "\n";
  }
  //connect components to make one tree
  sort(centers.rbegin(),centers.rend());
  int v = centers[0].s;
//   cout << v << "\n";
  for(int i=1;i<centers.size();i++){
//     cout  << centers[i].s << "\n";
    adjList.at(v).pb({centers[i].s,l});
    adjList.at(centers[i].s).pb({v,l});
  }
  bfs(0);
  bfs(now);
//   cout << dist << "\n";
  return dist;
}

// int main(){
//   int n=12,m=8,l=2;
//   int a[] = {0,8,2,5,5,1,1,10};
//   int b[] = {8,2,7,11,1,3,9,6};
//   int t[] = {4,2,4,3,7,1,5,3};
//   travelTime(n,m,l,a,b,t);
// }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:81:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<centers.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