Submission #1317588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317588		ElayV13	꿈 (IOI13_dreaming)	C++20	40 / 100	1096 ms	11124 KiB

dreaming

#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;

const int N = 100001;
const int INF = INT_MAX;

int n;
vector<pair<int,int>>G[N];
void add(int u,int v,int w)
{
   G[u].push_back({v,w});
   G[v].push_back({u,w});
}
bool vis[N];
vector<int>all;
void dfs(int v)
{
   all.push_back(v);
   vis[v]=1;
   for(pair<int,int> nxt : G[v])
   {
      int u=nxt.first;
      if(!vis[u]) dfs(u);
   }
}
int dis[N];
pair<int,int>get(int v)
{
   for(int u : all) dis[u]=INF;
   queue<int>q;
   q.push(v);
   dis[v]=0;
   while(!q.empty())
   {
      int node=q.front();
      q.pop();
      for(pair<int,int> nxt : G[node])
      {
         int u=nxt.first;
         int w=nxt.second;
         if(dis[node]+w<dis[u])
         {
            dis[u]=dis[node]+w;
            q.push(u);
         }
      }
   }
   pair<int,int>res={-INF,-INF};
   for(int u : all) res=max(res,{dis[u] , v});
   return res;
}
pair<int,int> find_center()
{
   vector<pair<int,int>>srt;
   for(int v : all) srt.push_back(get(v));
   sort(srt.begin(),srt.end());
   return {srt[0].second , srt[0].first};
}
pair<int,int> get_mx(int v)
{
   vector<int>d(n,INF);
   queue<int>q;
   d[v]=0;
   q.push(v);
   while(!q.empty())
   {
      int node=q.front();
      q.pop();
      for(pair<int,int> nxt : G[node])
      {
         int u=nxt.first;
         int w=nxt.second;
         if(d[node]+w<d[u])
         {
            d[u]=d[node]+w;
            q.push(u);
         }
      }
   }
   pair<int,int>res;
   for(int i=0;i<n;i++) res=max(res,{d[i],i});
   return res;
}
int get_dia()
{
   pair<int,int>mx1=get_mx(0);
   pair<int,int>mx2=get_mx(mx1.second);
   return mx2.first;
}
int travelTime(int N , int M , int L , int A[] , int B[] , int T[])
{
   n = N;
   for(int i = 0;i < M;i++) add(A[i] , B[i] , T[i]);
   vector < pair < int , int > > srt;
   for(int i = 0;i < N;i++)
   {
      if(vis[i]) continue;
      all.clear();
      dfs(i);
      pair < int , int > cw = find_center();
      int center = cw.first;
      int max_w = cw.second;
      srt.push_back({max_w , center});
   }
   sort(srt.rbegin() , srt.rend());
   for(int i = 1;i < srt.size();i++) add(srt[0].second , srt[i].second , L);
   return get_dia();
}

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