Submission #385665

#	Time	Username	Problem	Language	Result	Execution time	Memory
385665		Keshi	Rail (IOI14_rail)	C++17	56 / 100	491 ms	100592 KiB

rail

    //In the name of God
    #include <bits/stdc++.h>
    #include "rail.h"
    using namespace std;
     
    typedef int ll;
    typedef pair<ll, ll> pll;
     
    const ll maxn = 5100;
    const ll mod = 1e9 + 7;
    const ll inf = 1e9;
     
    #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
    #define pb push_back
    #define Mp make_pair
    #define F first
    #define S second
    #define Sz(x) ll((x).size())
    #define all(x) (x).begin(), (x).end()
     
    ll dis[maxn][maxn];
    bool isr[maxn];
     
    void findLocation(int n, int first, int loc[], int st[]){
    	for(ll i = 0; i < n; i++){
    		for(ll j = i + 1; j < n; j++){
    			dis[i][j] = dis[j][i] = getDistance(i, j);
    		}
    	}
    	ll x = 1;
    	for(ll i = 1; i < n; i++){
    		if(dis[0][i] < dis[0][x]) x = i;
    	}
    	st[0] = 1;
    	for(ll i = 1; i < n; i++){
    		if(dis[0][x] > dis[x][i] || x == i || dis[0][i] != dis[0][x] + dis[x][i]) isr[i] = 1;
    	}
    	while(true){
    		ll y = -1;
    		for(ll i = 1; i < n; i++){
    			if(st[i]) continue;
    			if(!isr[i]) continue;
    			if(y == -1 || dis[0][y] > dis[0][i]) y = i;
    		}
    		if(y == -1) break;
    		st[y] = 2;
    		loc[y] = dis[0][y];
    		ll z = 0;
    		for(ll i = 0; i < n; i++){
    			if(i == y) continue;
    			if(dis[y][i] < dis[y][z]) z = i;
    		}
    		if(st[z]) continue;
    		loc[z] = 2 * dis[0][y] - dis[0][z];
    		st[z] = 1;
    		for(ll i = 0; i < n; i++){
    			if(st[i]) continue;
    			if(!isr[i]) continue;
    			if(dis[y][i] < dis[z][i]){
    				st[i] = 1;
    				loc[i] = 2 * dis[0][y] - dis[0][i];
    			}
    		}
    	}
    	while(true){
    		ll y = -1;
    		for(ll i = 1; i < n; i++){
    			if(isr[i] || st[i]) continue;
    			if(y == -1 || dis[x][y] > dis[x][i]) y = i;
    		}
    		if(y == -1) break;
    		st[y] = 1;
    		loc[y] = dis[0][x] - dis[x][y];
    		ll z = 0;
    		for(ll i = 0; i < n; i++){
    			if(i == y) continue;
    			if(dis[y][i] < dis[y][z]) z = i;
    		}
    		if(st[z]) continue;
    		loc[z] = dis[0][x] - (2 * dis[x][y] - dis[x][z]);
    		st[z] = 2;
    		for(ll i = 0; i < n; i++){
    			if(isr[i] || st[i]) continue;
    			if(dis[y][i] < dis[z][i]){
    				st[i] = 2;
    				loc[i] = dis[0][x] - (2 * dis[x][y] - dis[x][i]);
    			}
    		}
    	}
    	loc[0] = 0;
    	for(ll i = 0; i < n; i++){
    		loc[i] += first;
    	}
    	return;
    }
     
    /*int main(){
        fast_io;
     
     
     
        return 0;
    }*/

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