| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 65515 |
2018-08-07T19:51:57 Z |
XmtosX |
Race (IOI11_race) |
C++17 |
|
25 ms |
23928 KB |
#include <bits/stdc++.h>
#include "race.h"
//#include "graderlib.c"
using namespace std;
const int MAXN=2e5+5;
int n,sz[MAXN],lvl[MAXN],mx,st,sprs[MAXN][20],par[MAXN];
int sum[MAXN][20];
int ans=1e9;
pair<int,int> c[MAXN];
bool yes,vis[MAXN];
vector <pair<int,int> > v[MAXN];
vector <int> here[MAXN];
vector <pair<int,pair<int,int> > > cen[MAXN];
set<pair<int,pair<int,int> > > s[MAXN];
set<pair<int,pair<int,int> > > :: iterator it;
void init (int x,int p,int w)
{
sz[x]=1;
lvl[x]=lvl[p]+1;
if (yes)
{
sprs[x][0]=p;
sum[x][0]=w;
for (int i=1;i<20;i++)
{
sprs[x][i]=sprs[sprs[x][i-1]][i-1];
sum[x][i]=sum[x][i-1]+(sum[sprs[x][i-1]][i-1]);
}
}
for (int i=0;i<v[x].size();i++)
{
int nxt=v[x][i].first;
if (nxt!=p)
{
init(nxt,x,v[x][i].second);
sz[x]+=sz[nxt];
}
}
}
pair<int,int> lca (int x,int y)
{
if (lvl[x]<lvl[y])
swap(x,y);
if (y==n)
return make_pair(0,0);
int a=0,b=0;
for (int i=19;i>=0;i--)
{
if (lvl[sprs[x][i]]>=lvl[y])
{
a+= (sum[x][i]);
x=sprs[x][i];
b+=(1<<i);
}
}
if (x==y)
{
return make_pair(a,b);
}
for (int i=19;i>=0;i--)
{
if (sprs[x][i]!=sprs[y][i])
{
a+= (sum[x][i]+sum[y][i]);
x=sprs[x][i];
y=sprs[y][i];
b+= (1<<i)*2;
}
}
b+=2;
a+= (sum[x][0]+sum[y][0]);
return make_pair(a,b);
}
void dfs (int x,int p,int N,int P,int X)
{
int maxx=0;
if (N==1)
{
cen[x].push_back({P,lca(P,x)});
cen[P].push_back({x,lca(P,x)});
vis[x]=true;
return ;
}
for (int i=0;i<v[x].size();i++)
{
int nxt=v[x][i].first;
if (lvl[nxt]>lvl[x]&&!vis[nxt])
{
maxx=max(maxx,sz[nxt]);
}
else if (lvl[nxt]>=lvl[X]&&!vis[nxt])
{
maxx=max(maxx,sz[X]-sz[x]);
}
}
if (maxx<=N/2)
{
vis[x]=true;
cen[P].push_back({x,lca(P,x)});
cen[x].push_back({P,lca(P,x)});
for (int i=0;i<v[x].size();i++)
{
int nxt=v[x][i].first;
if (lvl[nxt]>lvl[x]&&!vis[nxt])
{
dfs(nxt,x,sz[nxt],x,nxt);
}
else if (lvl[X]<=lvl[nxt]&&!vis[nxt])
{
dfs(nxt,x,sz[X]-sz[x],x,X);
}
}
return;
}
for (int i=0;i<v[x].size();i++)
{
int nxt=v[x][i].first;
if (nxt!=p&&!vis[nxt])
{
dfs(nxt,x,N,P,X);
}
}
}
void init1(int x,int p,pair<int,int> pp)
{
par[x]=p;
lvl[x]=lvl[p]+1;
c[x]= pp;
here[lvl[x]].push_back(x);
for (int i=0;i<cen[x].size();i++)
{
int nxt= (cen[x][i].first);
if (nxt!=p)
init1(nxt,x,cen[x][i].second);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;
for (int i=0;i<=n;i++)
{
for (int j=0;j<20;j++)
sprs[i][j]=n;
}
for (int i=0;i<n-1;i++)
{
v[H[i][1]].push_back({H[i][0],L[i]});
v[H[i][0]].push_back({H[i][1],L[i]});
}
init(0,n,0);
for (int i=0;i<n;i++)
{
int maxx=0;
for (int j=0;j<v[i].size();j++)
{
int nxt=v[i][j].first;
if (lvl[nxt]>lvl[i])
{
maxx=max(maxx,sz[nxt]);
}
else
{
maxx=max(maxx,sz[0]-sz[i]);
}
}
if (maxx<=n/2)
{
st=i;
break;
}
}
yes=true;
init(st,n,0);
dfs(st,-1,n,n,st);
init1(st,n,make_pair(0,0));
for (int i=0;i<n;i++)
{
s[i].insert({1e9,{1e9,1e9}});
s[i].insert({0,{0,N}});
}
for (int i=30;i>0;i--)
{
for (int j=0;j<here[i].size();j++)
{
int x=here[i][j];
int k=0;
int cnt=0;
if (x==n)
continue;
//cout <<x<<" ";
while (par[x]!=n)
{
cnt+= c[x].second;
k+= c[x].first;
pair<int,pair<int,int> > p;
if (k>K)
break;
p.first=k;
p.second= {cnt,x};
it= s[par[x]].lower_bound(p);
if ((*it).first==k&&(*it).second.second==x)
{
if ((*it).second.first<cnt)
break;
s[par[x]].erase(it);
}
s[par[x]].insert(p);
x=par[x];
}
}
//cout <<endl;
}
for (int i=0;i<n;i++)
{
int k=0;
int cnt=0;
int x=i;
while (par[x]!=n)
{
cnt+= c[x].second;
k+= c[x].first;
pair<int,pair<int,int> > p;
if (k>K)
break;
p.first=K-k;
p.second= {0,0};
it= s[par[x]].lower_bound(p);
if ((*it).first==p.first)
{
if ((*it).second.second==x)
it++;
if ((*it).first==p.first)
ans=min(ans,cnt+(*it).second.first);
}
x=par[x];
}
}
if (ans==1e9)
ans=-1;
return ans;
}
/*
int main()
{
return _main(best_path);
}
*/
Compilation message
race.cpp: In function 'void init(int, int, int)':
race.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int, int)':
race.cpp:87:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
race.cpp:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
race.cpp:118:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
race.cpp: In function 'void init1(int, int, std::pair<int, int>)':
race.cpp:133:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<cen[x].size();i++)
~^~~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:157:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0;j<v[i].size();j++)
~^~~~~~~~~~~~
race.cpp:186:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0;j<here[i].size();j++)
~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
