제출 #385960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
385960		PedroBigMan	기지국 (IOI20_stations)	C++14	10 / 100	1233 ms	1192 KiB

stations

#include "stations.h"
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}

class Tree
{
    public:
    ll N; 
    vector<ll> p; 
    vector<vector<ll> > sons;
    vector<vector<ll> > adj;
    ll root;
    vector<bool> visited;
    vector<ll> DFSarr1; //DFS Array
	vector<pl> pos;
    
    Tree(vector<vector<ll> > ad, ll r=0LL)
    {
        N=ad.size(); root=r; adj=ad;
        REP(i,0,N) {visited.pb(false);}
        vector<ll> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1);pos.pb({-1,-1});}
        DFS_Build(r,r);
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
    }
    
    void DFS_Build(ll s, ll par)
    {
		pos[s].ff=DFSarr1.size();
        DFSarr1.pb(s); 
        p[s]=par;
        visited[s]=true;
        REP(i,0,adj[s].size())
        {
            if(adj[s][i]==par) {continue;}
            sons[s].pb(adj[s][i]);
            DFS_Build(adj[s][i],s);
        }
		pos[s].ss=DFSarr1.size()-1;
        return;
    }
};

inline ll f(ll x)
{
	ll mil=1000;
	ll a = x/mil; ll b =x%mil;
	ll ans  =((2001-a)*a)/2 + (b-a);
	return ans;
}

inline ll invf(ll x)
{
	ll a,b; a=-1;
	REP(i,0,1000)
	{
		ll val = (i*(1999-i))/2;
		if(val>x) {a=i-1; break;}
	}
	if(a==-1) {a=999;}
	ll val = (a*(1999-a))/2; b=x-val;
	ll mil=1000;
	ll ans = mil*a+b;
	return ans;
}

vector<ll> label(ll N, ll k, vector<ll> u, vector<ll> v) 
{
	vector<ll> xx; vector<vector<ll> > adj; REP(i,0,N) {adj.pb(xx);}
	REP(i,0,N-1) {adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]);}
	Tree T(adj); 
	vector<ll> label; 
	ll mil=1000;
	REP(i,0,N) {label.pb(T.pos[i].ff*mil+T.pos[i].ss);}
	REP(i,0,N) {label[i]=f(label[i]);}
	REP(i,0,N) {label[i]=invf(label[i]);}
	return label;
}

ll find_next_station(ll s, ll t, vector<ll> c) 
{
	vector<pl> inter; pl self; pl target;
	ll mil=1000;
	vector<pl> poss;
	REP(i,0,c.size()) {c[i]=invf(c[i]);}
	REP(i,0,c.size()) {c[i]=f(c[i]);}
	s=invf(s); t=invf(t); s=f(s); t=f(t);
	self={s/mil,s%mil};
	REP(i,0,c.size()) {inter.pb({c[i]/mil,c[i]%mil});}
	target={t/mil,t%mil}; 
	ll beg = min_element(whole(inter))->ff;
	ll maxend =-1;  ll ind;
	REP(i,0,inter.size()) {if(inter[i].ff==beg && inter[i].ss>maxend) {maxend=inter[i].ss; ind=i;}}
	REP(i,0,inter.size())
	{
		if(i==ind) {continue;}
		if(target.ff>=inter[i].ff && target.ss<=inter[i].ss) {return c[i];}
	}
	return c[ind];
}

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

stations.cpp: In function 'll find_next_station(ll, ll, std::vector<int>)':
stations.cpp:142:14: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
  142 |  return c[ind];
      |              ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 10 / 10
• Subtask 5: 0 / 61