Submission #691517

#	Time	Username	Problem	Language	Result	Execution time	Memory
691517		Khizri	Rail (IOI14_rail)	C++17	56 / 100	2470 ms	166176 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
const int mxn=5000+5;
int dp[mxn][mxn],color[mxn],dis[mxn];
int ask(int i,int j){
    if(i>j) swap(i,j);
    if(i==j) return 0;
    if(dp[i][j]) return dp[i][j];
    return dp[i][j]=getDistance(i,j);
}
void findLocation(int n, int first, int pos[], int st[])
{
    int mx=1e5,idx=0;
    for(int i=1;i<n;i++){
        if(ask(0,i)<mx){
            mx=ask(0,i);
            idx=i;
        }
    }
    for(int i=0;i<n;i++){
        dis[i]=1e9;
    }
    pos[0]=first;
    st[0]=1;
    dis[0]=0;
    priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>>q;
    q.push({0,{0,0}});
    while(q.size()){
        pair<int,pii>pp=q.top();
        int u=pp.S.F,p=pp.S.S;
        q.pop();
        if(color[u]) continue;
        if(u!=p){
            color[u]=1;
            if(st[p]==1){
                st[u]=2;
                pos[u]=pos[p]+ask(p,u);
            }
            else{
                st[u]=1;
                pos[u]=pos[p]-ask(p,u);
            }
        }
        else{
            color[u]=1;
        }
        for(int i=0;i<n;i++){
            if(!color[i]&&dis[i]>ask(u,i)){
                q.push({ask(u,i),{i,u}});
                dis[i]=ask(u,i);
            }
        }
    }
}
/*
3
8
1 7
1 1
2 3
1 5
2 9
2 10
1 12
2 14
*/

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:26:16: warning: variable 'idx' set but not used [-Wunused-but-set-variable]
   26 |     int mx=1e5,idx=0;
      |                ^~~

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