Submission #877192

#	Time	Username	Problem	Language	Result	Execution time	Memory
877192		fanwen	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	309 ms	53152 KiB

riggedroads

#include <bits/stdc++.h>

using namespace std;
int dd[300005];
int sz[300005],cha[300005];
int head[300005];
int sauhld[300005];
int pos[300005],maxx[300005];
int timee;
vector<int>g[300005];
pair<int,int>tree[600005];
int lim=300000;
void upd(int p,int value,int pos) {
        p--;
  for (tree[p += lim] ={value,pos}; p > 1; p >>= 1) tree[p>>1] =min(tree[p] , tree[p^1]);
}
pair<int,int>query(int l, int r) {
pair<int,int>res={1e9,0};
if(l>r)return res;
  l--;
  for (l += lim, r += lim; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = min(res,tree[l++]);
    if (r&1) res = min(res,tree[--r]);
  }
  return res;
}
int vt[300005];
struct canh
{
int u,v,c;
}e[300005];
int db[300005];
int id[300005];
int n,m;
void dfs(int u,int pa)
{
sz[u]=1;
cha[u]=pa;
maxx[u]=0;
int vtmax=0;
for(int i=0;i<g[u].size();i++)
if(g[u][i]!=pa)
{
int v=g[u][i];
dfs(v,u);
sz[u]+=sz[v];
if(sz[v]>maxx[u]){vtmax=i;maxx[u]=sz[v];}
}
swap(g[u][0],g[u][vtmax]);
}
void hld(int u)
{
timee++;pos[u]=timee;
vt[timee]=u;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(cha[v]==u)
{
if(2*sz[v]>=sz[u]&&i==0)
{
head[v]=head[u];
sauhld[v]=sauhld[u];
}
else
{
head[v]=v;
sauhld[v]=sauhld[u]+1;
}
hld(v);
}
}}
bool cmp(int a,int b)
{
return id[a]<id[b];
}
int cur=0;
void update(int u, int v)
{
vector<int>vec;
if(sauhld[u]<sauhld[v])swap(u,v);
while(sauhld[u]>sauhld[v])
{
while(1)
{
auto[c,uu]=query(pos[head[u]],pos[u]);
if(c==1e9)break;
vec.push_back(uu);
upd(pos[uu],1e9,0);
}
u=cha[head[u]];
}
while(head[u]!=head[v])
{
while(1)
{
auto[c,uu]=query(pos[head[u]],pos[u]);
if(c==1e9)break;
vec.push_back(uu);
upd(pos[uu],1e9,0);
}
u=cha[head[u]];
while(1)
{
auto[c,uu]=query(pos[head[v]],pos[v]);
if(c==1e9)break;
vec.push_back(uu);
upd(pos[uu],1e9,0);
}v=cha[head[v]];
}
if(pos[u]<pos[v])swap(u,v);
while(1)
{
auto[c,uu]=query(pos[v]+1,pos[u]);
if(c==1e9)break;
vec.push_back(uu);
upd(pos[uu],1e9,0);
}
sort(vec.begin(),vec.end(),cmp);
for(auto vv:vec)
{
e[id[vv]].c=cur+1;cur++;
}
}
int main()
{

ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>e[i].u>>e[i].v;
}
for(int i=1;i<n;i++)
{
cin>>db[i];
dd[db[i]]=1;
g[e[db[i]].u].push_back(e[db[i]].v);
g[e[db[i]].v].push_back(e[db[i]].u);
}
sauhld[1]=head[1]=1;
dfs(1,0);
hld(1);
for(int i=2;i<=n;i++)upd(pos[i],0,i);
for(int i=1;i<n;i++)
{
auto[u,v,_]=e[db[i]];
if(u==cha[v])swap(u,v);
id[u]=db[i];
}
for(int i=1;i<=m;i++)
{
auto[u,v,_]=e[i];
if(dd[i]==1)
{
if(u==cha[v])swap(u,v);
if(query(pos[u],pos[u]).first==0){e[i].c=cur+1;cur++;upd(pos[u],1e9,0);}
}
else
{
update(u,v);
e[i].c=cur+1;
cur++;
}
}
for(int i=1;i<=m;i++)cout<<e[i].c<<" ";
    return 0;
}

Compilation message (stderr)

riggedroads.cpp: In function 'void dfs(int, int)':
riggedroads.cpp:41:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 | for(int i=0;i<g[u].size();i++)
      |             ~^~~~~~~~~~~~
riggedroads.cpp: In function 'void hld(int)':
riggedroads.cpp:55:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 | for(int i=0;i<g[u].size();i++)
      |             ~^~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32