제출 #117000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117000		baluteshih	철로 (IOI14_rail)	C++14	100 / 100	77 ms	760 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cerr << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

/*
1
4
1 1
2 4
2 7
2 9

2
6
1 3
2 6
2 7
1 1
1 0
2 8
*/ 

const int INF=1e9;

int gd(int i,int j)
{
	return getDistance(i,j);
}

void findLocation(int N, int first, int location[], int stype[])
{
	location[0]=first,stype[0]=1;
	set<int> loc[3];
	if(N==1) return;
	vector<int> d0(N,0),d1(N,0),vR,vL;
	deque<pii> vis;
	for(int i=1;i<N;++i)
		d0[i]=gd(0,i),vis.pb(MP(d0[i],i));
	sort(ALL(vis));
	int x=vis[0].S,tpR,tpL;
	vis.pop_front(),location[x]=d0[x]+first,stype[x]=2;
	for(int i=1;i<N;++i)
		if(i!=x)
			d1[i]=gd(i,x);
	while(!vis.empty())
	{
		auto tmp=vis[0].S;
		vis.pop_front();
		if(d0[tmp]-d1[tmp]==d0[x])
			if(d1[tmp]<=d0[x])
				location[tmp]=location[x]-d1[tmp],stype[tmp]=1;
			else
				if(vL.empty())
					location[tmp]=first+2*d0[x]-d0[tmp],stype[tmp]=1,vL.pb(location[tmp]),tpL=tmp;
				else
				{
					int dis=gd(tpL,tmp),delta=location[tpL]+(d0[tpL]+dis-d0[tmp])/2;
					int p=*lower_bound(vL.rbegin(),vL.rend(),delta);
					if(p!=delta)
						location[tmp]=first+2*d0[x]-d0[tmp],stype[tmp]=1,vL.pb(location[tmp]),tpL=tmp;
					else
						location[tmp]=location[tpL]+dis,stype[tmp]=2;
				}
		else
			if(vR.empty())
				location[tmp]=d0[tmp]+first,stype[tmp]=2,vR.pb(location[tmp]),tpR=tmp;
			else
			{
				int dis=gd(tpR,tmp),delta=location[tpR]-(d0[tpR]+dis-d0[tmp])/2;
				int p=*lower_bound(ALL(vR),delta);
				if(p!=delta)
					location[tmp]=d0[tmp]+first,stype[tmp]=2,vR.pb(location[tmp]),tpR=tmp;
				else
					location[tmp]=location[tpR]-dis,stype[tmp]=1;
			}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:39:24: warning: 'tpL' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return getDistance(i,j);
                        ^
rail.cpp:52:21: note: 'tpL' was declared here
  int x=vis[0].S,tpR,tpL;
                     ^~~
rail.cpp:39:24: warning: 'tpR' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return getDistance(i,j);
                        ^
rail.cpp:52:17: note: 'tpR' was declared here
  int x=vis[0].S,tpR,tpL;
                 ^~~

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