Submission #1317598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317598		ElayV13	꿈 (IOI13_dreaming)	C++20	100 / 100	179 ms	29720 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];
map<pair<int,int>,int>dsc;
void add(int u,int v,int w)
{
   dsc[{u,v}]=w;
   dsc[{v,u}]=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] , u});
   return res;
}
vector<int> get_path(int u,int v)
{
   for(int u : all) dis[u]=INF;
   queue<int>q;
   q.push(u);
   dis[u]=0;
   while(!q.empty())
   {
      int node=q.front();
      q.pop();
      for(pair<int,int> nxt : G[node])
      {
         int u=nxt.first;
         if(dis[node]+1<dis[u])
         {
            dis[u]=dis[node]+1;
            q.push(u);
         }
      }
   }
   vector<int>res;
   int cur_node=v;
   while(1)
   {
      res.push_back(v);
      if(v==u) break;
      int mn=INF;
      for(pair<int,int> node : G[v]) mn=min(mn,dis[node.first]);
      for(pair<int,int> node : G[v])
      {
         if(dis[node.first]==mn)
         {
            v=node.first;
            break;
         }
      }
   }
   return res;
}
pair<int,int> find_center()
{
   pair<int,int>mx1=get(all[0]);
   pair<int,int>mx2=get(mx1.second);
   int u=mx1.second;
   int v=mx2.second;
   int tot=mx2.first;
   int cur=0;
   vector<int>path=get_path(u,v);
   if(path.size()==1)
   {
      return {path[0],0};
   }
   vector<pair<int,int>>srt;
   for(int i=1;i<path.size();i++)
   {
      int wg=dsc[{path[i-1],path[i]}];
      cur+=wg;
      tot-=wg;
      srt.push_back({max(cur,tot),path[i]});
   }
   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: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23