Submission #679390

#	Time	Username	Problem	Language	Result	Execution time	Memory
679390		Cross_Ratio	Rail (IOI14_rail)	C++14	56 / 100	390 ms	98640 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
int N;
int d1, d2;
int dis[5005][2];
int p1, p2;
int dist[5005][5005];
int getD(int x, int y) {
    if(x==y) return 0;
    if(dist[x][y]==0) {
        if(dist[y][x]!=0) {
            dist[x][y] = dist[y][x];
        }
        else dist[x][y] = getDistance(x, y);
    }
    return dist[x][y];
}
void findLocation(int _N, int _f, int location[], int stype[]) {
    p1 = 0, d1 = _f;
    N = _N;
    stype[0] = 1;
    location[0] = d1;
    if(N==1) return;
    int i, j;
    for(i=0;i<N;i++) {
        for(j=0;j<N;j++) {
            dist[i][j] = 0;
        }
        dis[i][0] = dis[i][1] = 0;
    }
    for(i=1;i<N;i++) {
        dis[i][0] = getD(0, i);
    }
    int mi = 2e9;
    for(i=1;i<N;i++) {
        if(mi > dis[i][0]) {
            mi = dis[i][0];
            p2 = i;
        }
    }
    d2 = d1 + dis[p2][0];
    stype[p2] = 2;
    location[p2] = d2;
    // L        (p1, d1)   (p2, d2)         R
    for(i=0;i<N;i++) {
        dis[i][1] = getD(p2, i);
    }
    mi = 2e9;
    for(i=0;i<N;i++) {
        if(i==p2) continue;
        if(mi > dis[i][1]) {
            mi = dis[i][1];
            p1 = i;
        }
    }
    stype[p1] = 1;
    location[p1] = d1 = d2 - mi;
    for(i=0;i<N;i++) {
        dis[i][0] = getD(p1, i);
    }
    int d = d2 - d1;
    vector<int> V1, V2;
    for(i=0;i<N;i++) {
        if(i==p1||i==p2) continue;
        //assert(abs(dis[i][0] - dis[i][1])==d);
        if(dis[i][0] > dis[i][1]) {
            V2.push_back(i);
        }
        else {
            V1.push_back(i);
        }
    }
    while(V1.size()) {
        int mi = 2e9, pt = -1;
        for(int k : V1) {
            if(mi > dis[k][0]) {
                mi = dis[k][0];
                pt = k;
            }
        }
        assert(pt!=-1);
        stype[pt] = 2;
        location[pt] = d1 + mi;
        vector<int> V;
        for(int k : V1) {
            if(k==pt) continue;
            int d = getD(pt, k);
            if(dis[k][0] == mi + d) {
                stype[k] = 1;
                location[k] = d1 + mi - d;
            }
            else V.push_back(k);
        }
        V1 = V;
    }
    while(V2.size()) {
        int mi = 2e9, pt = -1;
        for(int k : V2) {
            if(mi > dis[k][1]) {
                mi = dis[k][1], pt = k;
            }
        }
        assert(pt!=-1);
        stype[pt] = 1;
        location[pt] = d2 - mi;
        vector<int> V;
        for(int k : V2) {
            int d = getD(pt, k);
            if(k==pt) continue;
            if(dis[k][1]==mi + d) {
                stype[k] = 2;
                location[k] = d2 - mi + d;
            }
            else V.push_back(k);
        }
        V2 = V;
    }
    for(i=0;i<N;i++) {
        assert(stype[i]==1||stype[i]==2);
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:62:9: warning: unused variable 'd' [-Wunused-variable]
   62 |     int d = d2 - d1;
      |         ^

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