Submission #1069045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069045		NemanjaSo2005	Rail (IOI14_rail)	C++17	100 / 100	88 ms	98964 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;
bool CjeA=false;
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){
   if(CjeA)
      return dist(A,x);
   return dist(A,x)-dist(A,B)+D;
}
set<int> PC,PD;
/*bool prov(int l,int r,int x){
   if(stations[l].location>stations[r].location)
      swap(l,r);
   return stations[l].location < stations[x].location and stations[x].location<stations[r].location;
}*/
bool lint(int l,int r,int x){ /// Unutra je D
  // cout<<"LEFT INTERVAL "<<l<<" "<<r<<" "<<x<<endl;
 // return prov(l,r,x);
   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;
  // return prov(l,r,x);
   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;
      idxD=xx;
   }
   if(poz[xx]<poz[A]){
      CjeA=true;
      idxC=xx;
   }
//   cout<<stations[A].location<<" "<<stations[A].type<<endl;
 //  cout<<stations[B].location<<" "<<stations[B].type<<endl;
  // cout<<stations[xx].location<<" "<<stations[xx].type<<endl;
   /*if(stations[xx].location!=poz[xx]){
      cout<<"AJO"<<endl;
   }*/
   while(Q.size()){
      int x=Q.front();
      Q.pop();
     // cout<<x<<endl;
     // cout<<stations[x].location<<" "<<stations[x].type<<endl;
      if(rint(A,B,x)){
         //cout<<x<<" A"<<endl;
         tip[x]=1;
         poz[x]=poz[B]-dist(x,B);
         PC.insert(poz[x]);
         continue;
      }

     // cout<<distc(x)<<" "<<dist(x,B)<<endl;

      if(distc(x)>dist(x,B)){
       //  cout<<"LEVO"<<endl;
         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{
       //  cout<<"DESNO"<<endl;
         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;
         }
      }/*
      if(stations[x].location!=poz[x])
         exit(-1);*/
   }
   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:84: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]
   84 |    for(int i=1;i<V.size();i++)
      |                ~^~~~~~~~~

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