Submission #96774

#	Time	Username	Problem	Language	Result	Execution time	Memory
96774		SecretAgent007	Rail (IOI14_rail)	C++17	30 / 100	80 ms	864 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 R;
	vector<int> visited(N,false);
	visited[0] = true;
	int p = -1;
	while(1){
        int maxi = INT_MAX;
        for(int i = 1; i < N; i++){
            if(dist(0,i) < maxi && !visited[i] && dist(0,i) != dist(0,p)+dist(p,i)){
                maxi = dist(0,i);
                R = i;
            }
        }
        if(maxi == INT_MAX)
            break;
        if(p == -1) p = R;
        stype[R] = 2;
        location[R] = first+dist(0,R);
        visited[R] = true;
        for(int i = 1; i < N; i++){
            if(!visited[i] && dist(0,i) == dist(0,R)+dist(R,i) && dist(R,i) < dist(0, R)){
                location[i] = first+dist(0,R)-dist(R,i);
                stype[i] = 1;
                visited[i] = true;
            }
        }
	}
	int L = 0;
	while(1){
        int maxi = INT_MAX;
        for(int i = 1; i < N; i++){
            if(dist(0,i) < maxi && !visited[i]){
                maxi = dist(0,i);
                L = i;
            }
        }
        if(maxi == INT_MAX) break;
        location[L] = first-(dist(0,L)-2*dist(0,p));
        stype[L] = 1;
        visited[L] = true;
        for(int i = 1; i < N; i++){
            if(!visited[i] && dist(0,i) == dist(0,L)+dist(L,i) && dist(L,i) < dist(0,L)-2*dist(0,p)){
                stype[i] = 2;
                location[i] = location[L]+dist(L,i);
                visited[i] = true;
            }
        }
	}
}
/*
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];
    for(int i = 0; i < n; i++){
        location[i] = INT_MAX;
        stype[i] = INT_MAX;
    }
    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:99:1: warning: "/*" within comment [-Wcomment]
 /*
  
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:27:6: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int R;
      ^

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