Submission #1007389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007389		tosivanmak	Rail (IOI14_rail)	C++17	30 / 100	60 ms	197980 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

ll dist[5005][5005];
ll loc[1000005];
ll getdist(ll i, ll j){
    if(i==j)return 0;
    if(dist[i][j])return dist[i][j];
    dist[i][j]=dist[j][i]=getDistance(i,j);
    return dist[i][j];
}
void findLocation(int n, int first, int location[],int stype[]){
    location[0]=first,stype[0]=1;
    loc[first]=0;
    if(n==1)return;
    int st=0;
    vector<pair<ll,ll> >from,hi,mi;
    for(int i=1;i<n;i++){
        from.pb({getdist(st,i),i});
    }
    sort(from.begin(),from.end());
    from.clear();
    ll req=from[0].second;
    location[req]=location[0]+getdist(0,req);stype[req]=2;
    for(int i=0;i<n;i++){
        if(i==st||i==req)continue;
        if(getdist(st,i)==getdist(req,i)+getdist(st,req)&&getdist(req,i)<getdist(st,req)){
            stype[i]=1;location[i]=location[req]-getdist(req,i);continue;
        }
        if(getdist(st,i)<getdist(req,i)){
            mi.push_back({getdist(st,i),i});
        }
        else{
            hi.push_back({getdist(req,i),i});
        }
    }
    sort(hi.begin(),hi.end());
    sort(mi.begin(),mi.end());
    ll init,init2;
    for(int i=0;i<hi.size();i++){
        if(i==0){
            ll nd=hi[i].second;
            stype[nd]=1,location[nd]=location[req]-getdist(req,nd);
            init=nd;continue;
        }
        ll nd=hi[i].second;
        ll v=getdist(init,nd)+getdist(req,nd)-getdist(init,req);v/=2;
        if(location[init]+getdist(init,nd)-v!=location[init]){
            location[nd]=location[req]-getdist(req,nd);
            stype[nd]=1;init=nd;
        }
        else{
            location[nd]=location[init]+v;
            stype[nd]=2;
        }
    }
    for(int i=0;i<mi.size();i++){
        if(i==0){
            ll nd=mi[i].second;
            stype[nd]=2,location[nd]=location[st]+getdist(st,nd);
            init=nd;continue;
        }
        ll nd=mi[i].second;
        ll v=getdist(init,nd)+getdist(st,nd)-getdist(init,st);v/=2;
        if(location[init]-getdist(init,nd)+v!=location[init]){
            location[nd]=location[st]+getdist(st,nd);
            stype[nd]=2;init=nd;
        }
        else{
            location[nd]=location[init]-v;
            stype[nd]=1;
            
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0;i<hi.size();i++){
      |                 ~^~~~~~~~~~
rail.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i<mi.size();i++){
      |                 ~^~~~~~~~~~
rail.cpp:42:13: warning: unused variable 'init2' [-Wunused-variable]
   42 |     ll init,init2;
      |             ^~~~~
rail.cpp:12:26: warning: 'init' may be used uninitialized in this function [-Wmaybe-uninitialized]
   12 |     dist[i][j]=dist[j][i]=getDistance(i,j);
      |                ~~~~~~~~~~^~~~~~~~~~~~~~~~~
rail.cpp:42:8: note: 'init' was declared here
   42 |     ll init,init2;
      |        ^~~~

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