Submission #1304633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304633		gurkot	Migrations (IOI25_migrations)	C++20	72.89 / 100	35 ms	1448 KiB

migrations

#include "migrations.h"
#include <iostream>
#include <vector>
using namespace std;
vector <int> gr[10000];
int dist[10000],X[14],Y[14];
int maxd,curd,x,y,faru;

void dfs(int pu, int u, int d){
 curd=max(curd,d);
 dist[u]=d;
 for (int i=0;i<(int)gr[u].size();i++){
  int v=gr[u][i];
  if (v!=pu) dfs(u,v,d+1);	
 }
}

int send_message(int N, int u, int pu) {
 int status,pos;
 gr[u].push_back(pu); gr[pu].push_back(u);
 if (u<N-28){
  return 0;  	
 } else 
 if (u==N-28){
  curd=0; dfs(-1,0,0); 
  for (int i=0;i<=u;i++) if (dist[i]==curd) { faru=i;break;}
  x=faru; 
  for (int i=0;i<14;i++) X[i]=faru%2, faru=faru/2;
  
  curd=0; dfs(-1,x,0); 
  for (int i=0;i<=u;i++) if (dist[i]==curd) {faru=i;break;}
  y=faru; maxd=curd;  
  for (int i=0;i<14;i++) Y[i]=faru%2, faru=faru/2;
  
  status=0;  	
  return X[0];
 } else
 if (u<N-14) {
  pos=u-(N-28);  curd=0; dfs(-1,u,0);
  if (curd>maxd) {
  	maxd=curd;
  	for (int i=0;i<=u;i++) 
	  if (dist[i]==curd && (i==x || i==y)) {faru=i;break;}
  	if (faru==x) X[pos]+=2,y=u;
  	        else X[pos]=4, x=u;
  } 	
  return X[pos];
 } else { //u>=N-14 && u<N
  pos=u-(N-14); 
  curd=0; dfs(-1,u,0);
  if (curd>maxd) {
  	maxd=curd;
  	for (int i=0;i<=u;i++) 
	  if (dist[i]==curd && (i==x || i==y)) {faru=i;break;}
  	if (faru==y) Y[pos]+=2,x=u;
  	        else Y[pos]=4, y=u;
  }   
  return Y[pos];
 } 
}

std::pair<int, int> longest_path(std::vector<int> S) {  
  int n=S.size();
  int x=0,y=0,h; 
  for (int i=n-28;i<n-14;i++)
   if (S[i]==4) x=i; else
   if (S[i]>1) S[i]-=2,y=i;
  for (int i=n-14;i<n;i++)
   if (S[i]==4) y=i; else
   if (S[i]>1) S[i]-=2,x=i;   

  if (x==0){
  	h=1;
  	for (int i=n-28;i<n-14;i++) x=x+h*S[i], h=h*2;
  } 
  if (y==0){
  	h=1;
  	for (int i=n-14;i<n;i++) y=y+h*S[i], h=h*2;
  }     
  pair <int,int> ans=make_pair(x,y);  
  return ans;
}

/*

30
0 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

*/

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 42.8897 / 70