Submission #1068990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068990		NemanjaSo2005	Rail (IOI14_rail)	C++17	8 / 100	94 ms	98904 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=5005;
int kesh[maxn][maxn],N,idxC,idxD,poz[maxn],tip[maxn],D,A,B;
vector<pair<int,int>> V;
queue<int> Q;
int dist(int a,int b){
   if(a==b)
      return 0;
   if(kesh[a][b]==-2){
    //  cout<<a<<" - "<<b<<": ";
      int x=getDistance(a,b);
     // cout<<x<<endl;
      kesh[a][b]=kesh[b][a]=x;
   }
   return kesh[a][b];
}
int distc(int x){
   return dist(A,x)-dist(A,B)+D;
}
set<int> PC,PD;
bool lint(int l,int r,int x){ /// Unutra je D
  // cout<<"LEFT INTERVAL "<<l<<" "<<r<<" "<<x<<endl;
   int p=poz[l]+dist(l,x);
   if(p>=poz[r])
      return false;
   auto it=PC.upper_bound(p);
   it--;
   int d=*it;
   if(poz[r]-d+p-d==dist(r,x))
      return true;
   return false;
}
bool rint(int l,int r,int x){ /// Unutra je C
   //cout<<"RIGHT INTERVAL "<<l<<" "<<r<<" "<<x<<endl;
   int p=poz[r]-dist(r,x);
   if(p<=poz[l])
      return false;
  // cout<<p<<endl;
   auto it=PD.upper_bound(p);
   int d=*it;
   //cout<<d<<endl;
   if(d-poz[l]+d-p==dist(l,x))
      return true;
   return false;
}
void findLocation(int n, int first, int location[], int stype[]){
   N=n;
   for(int i=0;i<N;i++)
      for(int j=0;j<N;j++)
         kesh[i][j]=-2;
   location[0]=first;
   stype[0]=1;
   if(N==1)
      return;
   if(N==2){
      stype[1]=2;
      location[1]=first+dist(0,1);
      return;
   }
   for(int i=1;i<N;i++)
      V.push_back({dist(0,i),i});
   sort(V.begin(),V.end());
   idxC=0;
   poz[0]=first;
   tip[0]=1;
   idxD=V[0].s;
   poz[idxD]=first+dist(0,idxD);
   tip[idxD]=2;
   for(int i=1;i<V.size();i++)
      Q.push(V[i].second);
   A=idxC;
   B=idxD;
   PC.insert(poz[A]);
   PD.insert(poz[B]);
   int xx=Q.front();
   Q.pop();
   if(dist(B,xx)+dist(A,B)==dist(A,xx)){
      tip[xx]=1;
      poz[xx]=poz[B]-dist(B,xx);
      PC.insert(poz[xx]);
      D=dist(B,xx);
   }
   else{
      tip[xx]=2;
      poz[xx]=poz[A]+dist(A,xx);
      PD.insert(poz[xx]);
      D=(dist(B,xx)-(dist(A,xx)-dist(A,B)))/2;
   }
   while(Q.size()){
      int x=Q.front();
      Q.pop();

      if(rint(A,B,x)){
         //cout<<x<<" A"<<endl;
         tip[x]=1;
         poz[x]=poz[B]-dist(x,B);
         PC.insert(poz[x]);
         continue;
      }

      if(distc(x)>dist(x,B)){
         if(lint(idxC,B,x)){
        //    cout<<x<<" B"<<endl;
            tip[x]=2;
            poz[x]=poz[idxC]+dist(idxC,x);
            PD.insert(poz[x]);
         }
         else{
          //  cout<<x<<" C"<<endl;
            tip[x]=1;
            poz[x]=poz[B]-dist(B,x);
            PC.insert(poz[x]);
            idxC=x;
         }
      }
      else{
         if(rint(A,idxD,x)){
         //   cout<<x<<" D"<<endl;
            tip[x]=1;
            poz[x]=poz[idxD]-dist(idxD,x);
            PC.insert(poz[x]);
         }
         else{
           // cout<<x<<" E"<<endl;
            tip[x]=2;
            poz[x]=poz[A]+dist(A,x);
            PD.insert(poz[x]);
            idxD=x;
         }
      }
   }
   for(int i=1;i<N;i++){
      location[i]=poz[i];
      stype[i]=tip[i];
   }
}
/*
3
15
1 8
1 1
1 2
1 3
2 4
2 5
1 6
2 7
2 9
2 10
1 11
1 12
2 13
1 14
2 15

1
4
1 1
2 4
2 7
2 9


2
6
1 3
2 6
2 7
1 1
1 0
2 8

3
8
1 1
1 3
2 10
1 12
2 18
2 19
1 25
2 26

*/

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:74:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    for(int i=1;i<V.size();i++)
      |                ~^~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44