Submission #96762

#	Time	Username	Problem	Language	Result	Execution time	Memory
96762		SecretAgent007	Rail (IOI14_rail)	C++17	0 / 100	71 ms	1016 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
/*
int diste[109][109];

int getDistance(int a, int b){
    return diste[a][b];
}
*/

int memo[109][109];

int dist(int a, int b){
    if(memo[a][b] != -1) return memo[a][b];
    return memo[a][b] = getDistance(a,b);
}

void findLocation(int N, int first, int location[], int stype[]){
	for(int i = 0; i < 109; i++){
        for(int j = 0; j < 109; j++){
            memo[i][j] = -1;
        }
	}
	stype[0] = 1;
	location[0] = first;
	int stat = 0;
	int maxi = INT_MAX;
	for(int i = 1; i < N; i++){
        if(maxi > dist(0,i)){
            maxi = dist(0,i);
            stat = i;
        }
	}
	int fS = stat;
	int fM = maxi;
	stype[stat] = 2;
	location[stat] = first+maxi;
	int Stat = 0;
	int Maxi = INT_MAX;
	for(int i = 1; i < N; i++){
        if(stat == i) continue;
        if(Maxi > dist(stat,i) && dist(stat, i) > maxi){
            Maxi = dist(stat, i);
            Stat = i;
        }
	}
	int Done = 3;
	stype[Stat] = 1;
	location[Stat] = first+maxi-Maxi;
	vector<bool> done(N,false);
	done[0] = true;
	done[stat] = true;
	done[Stat] = true;
	Maxi = Maxi-maxi;
	while(Done < N){
        //cout << "Donnée " << stat << ' ' << maxi << ' ' << Stat << ' ' << Maxi << endl;
        //cout << endl;
        for(int i = 1; i < N; i++){
            if(done[i]) continue;
            //cout << i << ' ' << dist(stat,i) << endl;
            if(dist(stat,i) < maxi && dist(0,i) == dist(0,stat)+dist(stat,i)){

                Done++;
                done[i] = true;
                location[i] = first+dist(0,stat)-dist(stat,i);
                stype[i] = 1;
            }
        }
        for(int i = 1; i < N; i++){
            if(done[i]) continue;
            //cout << dist(Stat, i) << ' ' << dist(0, i) << ' ' << dist(0,Stat) <<endl;
            if(dist(Stat, i) < Maxi && dist(Stat,i) == dist(0, i)-dist(0,Stat)){
                Done++;
                done[i] = true;
                location[i] = location[Stat]+dist(Stat,i);
                stype[i] = 2;
            }
        }
        //cout << endl;
        int tstat = -1;
        int tmax = INT_MAX;
        int tStat= -1;
        int tMax = INT_MAX;
        for(int i = 1; i < N; i++){
            if(done[i]) continue;
            if(dist(0,i) != dist(fS, i)+dist(0,fS) && dist(0,i) < tmax){
                tmax = dist(0,i);
                tstat = i;
            }else if(dist(0,i) == dist(fS, i)+dist(0,fS) && dist(0,i) < tMax){
                tMax = dist(0,i);
                tstat = i;
            }
        }
        if(tstat != -1){
            stype[tstat] = 2;
            location[tstat] = dist(0, tstat);
        }
        if(tStat != -1){
            stype[tStat] = 1;
            location[tStat] = first-(dist(0,tStat)-2*dist(0,fS));
        }
        stat = tstat;
        maxi = tmax-maxi;
        Stat = tStat;
        Maxi = tMax-2*dist(0, fS)-Maxi;
	}
}
/*
int main(){
    int n;
    cin >> n;
    int first;
    cin >> first;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> diste[i][j];
        }
    }
    int location[n];
    int stype[n];
    findLocation(n,first, location,stype);
    cout << endl;
    for(int a : location) cout << a << ' ';
    cout << endl;
    for(int a : stype) cout << a << ' ';
    cout << endl;
}*/
/*
5 4
0 12 4 15 7
12 0 8 3 11
4 8 0 11 3
15 3 11 0 14
7 11 3 14 0
*/

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:36:6: warning: unused variable 'fM' [-Wunused-variable]
  int fM = maxi;
      ^~

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