이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
* Prof.Nicola
**/
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define mp make_pair
#define F first
#define S second
#define REP(i,l,r) for(long long i=(l);i<(r);i++)
#define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)
const long dx[4]={1,0,-1,0},dz[4]={0,1,0,-1};
const long double pi=3.14159265359;
const long long mod=1e9+7;
long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;}
long long squared(long long x){return (x*x)%mod;}
long long power(long long x,long long p){if(p==0){return 1;}if(p%2==1){return (power(x,p-1)*x)%mod;}return squared(power(x,p/2));}
long long inv(long long x){return power(x,mod-2);}
template<class T>void re(T&x){cin>>x;}
template<class T1,class T2> void re(pair<T1,T2>&x){re(x.first);re(x.second);}
template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void re(deque<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void out(T x){cout<<x<<" ";}
template<class T1,class T2>void out(pair<T1,T2>x){out(x.first);out(x.second);cout<<endl;}
template<class T>void out(vector<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(deque<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(set<T>x){while(!x.empty()){out(*x.begin());x.erase(*x.begin());}cout<<endl;}
template<class T1,class T2>void out(map<T1,T2>x){while(!x.empty()){out(*x.begin());x.erase(x.begin()->first);}cout<<endl;}
template<class T>void out(queue<T>x){while(!x.empty()){out(x.front());x.pop();}cout<<endl;}
template<class T>void out(priority_queue<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;}
template<class T>void out(stack<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;}
template<class T>T cross(complex<T>x,complex<T>z){return (conj(x)*z).imag();}
template<class T>T dot(complex<T>x,complex<T>z){return (conj(x)*z).real();}
set<long long>::iterator T;
long long vLE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<=x){l+=z;}z/=2;}return l;}
long long vL(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<x){l+=z;}z/=2;}return l;}
long long vGE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return l;}l=vL(x,VT,l,r);if(l==r){return -1;}return l+1;}
long long vG(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return l;}l=vLE(x,VT,l,r);if(l==r){return -1;}return l+1;}
long long sLE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.begin()>x){return -1;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;}
long long sL(long long x,set<long long>&ST){if(*ST.begin()>=x){return -1;}if(ST.count(x)){T=ST.find(x);T--;return *T;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;}
long long sGE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.rbegin()<x){return -1;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;}
long long sG(long long x,set<long long>&ST){if(*ST.rbegin()<=x){return -1;}if(ST.count(x)){T=ST.find(x);T++;return *T;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;}
long k,ans=1e9;
vector<long long>len;
vector<pair<pair<long,long>,pair<long,long> > >mn;
struct tree
{
long long n;
vector<vector<pair<long,long> > >edges;
vector<long>depth,sz;
vector<bool>vis;
void scan0(long x,long p,long long l)
{
len[x]=l;
depth[x]=depth[p]+1;
sz[x]=1;
REP(i,0,edges[x].size()){
if(edges[x][i].F==p||vis[edges[x][i].F]){
continue;
}
scan0(edges[x][i].F,x,l+edges[x][i].S);
sz[x]+=sz[edges[x][i].F];
}
}
void scan(long x,long p,long long l,long h)
{
if(l>k){
return;
}
if(depth[x]<=mn[l].F.F){
if(mn[l].F.S==h){
mn[l].F.F=depth[x];
}
else{
mn[l].S=mn[l].F;
mn[l].F=mp(depth[x],h);
}
}
else if(depth[x]<mn[l].F.S){
if(mn[l].F.S!=h){
mn[l].S=mp(depth[x],h);
}
}
REP(i,0,edges[x].size()){
if(edges[x][i].F==p||vis[edges[x][i].F]){
continue;
}
scan(edges[x][i].F,x,l+edges[x][i].S,h);
}
}
void scan2(long x,long p,long long l,long h)
{
if(l>k){
return;
}
if(h==mn[k-l].F.S&&mn[k-l].S.S!=0){
ans=min(ans,depth[x]+mn[k-l].S.F);
}
else if(h!=mn[k-l].F.S){
ans=min(ans,depth[l]+mn[k-l].F.F);
}
REP(i,0,edges[x].size()){
if(edges[x][i].F==p||vis[edges[x][i].F]){
continue;
}
scan2(edges[x][i].F,x,l+edges[x][i].S,h);
}
}
void scan3(long x,long p,long long l,long h)
{
mn[l]=mp(mp(1e9,0),mp(1e9,0));
REP(i,0,edges[x].size()){
if(edges[x][i].F==p||vis[edges[x][i].F]){
continue;
}
scan3(edges[x][i].F,x,l+edges[x][i].S,h);
}
}
long centroid(long x,long p,long z)
{
long mx=0,node=x;
REP(i,0,edges[x].size()){
if(!vis[edges[x][i].F]&&edges[x][i].F!=p&&sz[edges[x][i].F]>mx){
mx=sz[edges[x][i].F];
node=edges[x][i].F;
}
}
if(mx<z){
return x;
}
return centroid(node,x,z);
}
void read(long nodes,vector<vector<pair<long,long> > >e)
{
n=nodes;
edges=e;
}
void build(long long root=1)
{
vis.clear();
vis.resize(n+1);
depth.clear();
depth.resize(n+1);
depth[0]=0;
sz.clear();
sz.resize(n+1);
scan0(root,0,0);
}
};
tree t;
void solve(long x)
{
t.scan0(x,0,0);
x=t.centroid(x,0,(t.sz[x]+1)/2);
t.vis[x]=true;
REP(i,0,t.edges[x].size()){
if(t.vis[t.edges[x][i].F]){
continue;
}
t.scan0(t.edges[x][i].F,0,t.edges[x][i].S);
t.scan(t.edges[x][i].F,0,t.edges[x][i].S,t.edges[x][i].F);
}
REP(i,0,t.edges[x].size()){
if(t.vis[t.edges[x][i].F]){
continue;
}
t.scan2(t.edges[x][i].F,0,t.edges[x][i].S,t.edges[x][i].F);
}
REP(i,0,t.edges[x].size()){
if(t.vis[t.edges[x][i].F]){
continue;
}
t.scan3(t.edges[x][i].F,0,t.edges[x][i].S,t.edges[x][i].F);
}
REP(i,0,t.edges[x].size()){
if(t.vis[t.edges[x][i].F]){
continue;
}
solve(t.edges[x][i].F);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
mn.resize(K+1);
mn[0]=mp(mp(0,1),mp(0,2));
REP(i,1,K){
mn[i]=mp(mp(1e9,0),mp(1e9,0));
}
k=K;
len.resize(N+1);
vector<vector<pair<long,long> > >e(N+1);
REP(i,0,N-1){
e[H[i][0]+1].push_back(mp(H[i][1]+1,L[i]));
e[H[i][1]+1].push_back(mp(H[i][0]+1,L[i]));
}
t.read(N,e);
t.build();
solve(1);
if(ans>=999999998){
return -1;
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In member function 'void tree::scan0(long int, long int, long long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
| ^
race.cpp:59:9: note: in expansion of macro 'REP'
59 | REP(i,0,edges[x].size()){
| ^~~
race.cpp: In member function 'void tree::scan(long int, long int, long long int, long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
| ^
race.cpp:86:9: note: in expansion of macro 'REP'
86 | REP(i,0,edges[x].size()){
| ^~~
race.cpp: In member function 'void tree::scan2(long int, long int, long long int, long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
| ^
race.cpp:104:9: note: in expansion of macro 'REP'
104 | REP(i,0,edges[x].size()){
| ^~~
race.cpp: In member function 'void tree::scan3(long int, long int, long long int, long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
| ^
race.cpp:114:9: note: in expansion of macro 'REP'
114 | REP(i,0,edges[x].size()){
| ^~~
race.cpp: In member function 'long int tree::centroid(long int, long int, long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
| ^
race.cpp:124:9: note: in expansion of macro 'REP'
124 | REP(i,0,edges[x].size()){
| ^~~
race.cpp: In function 'void solve(long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
| ^
race.cpp:158:5: note: in expansion of macro 'REP'
158 | REP(i,0,t.edges[x].size()){
| ^~~
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
| ^
race.cpp:165:5: note: in expansion of macro 'REP'
165 | REP(i,0,t.edges[x].size()){
| ^~~
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
| ^
race.cpp:171:5: note: in expansion of macro 'REP'
171 | REP(i,0,t.edges[x].size()){
| ^~~
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
| ^
race.cpp:177:5: note: in expansion of macro 'REP'
177 | REP(i,0,t.edges[x].size()){
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |