Submission #783537

#	Time	Username	Problem	Language	Result	Execution time	Memory
783537		1075508020060209tc	Railway (BOI17_railway)	C++14	100 / 100	144 ms	41148 KiB

railway

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define X first
#define Y second
int n;int Q;int K;
vector<int>e[500005];
int ar[500005];int br[500005];
vector<int>dfn;
int rmq[21][500005];
int dph[500005];
int rdfn[500005];
void dfs(int nw,int pa){
dfn.push_back(nw);
dph[nw]=dph[pa]+1;
for(int i=0;i<e[nw].size();i++){
    int v=nw^ar[e[nw][i]]^br[e[nw][i]];
    if(v==pa){continue;}
    dfs(v,nw);
    dfn.push_back(nw);
}
}
int lca(int a,int b){
int l=rdfn[a];int r=rdfn[b];
if(l>r){swap(l,r);}
int lg=__lg(r-l+1);
int ret=rmq[lg][l];
if(dph[ret]>dph[rmq[lg][r-(1<<lg)+1]]){
    ret=rmq[lg][r-(1<<lg)+1];
}
return ret;
}
int ptad[500005];
vector<int>ans;
int dp[500005];
void fdfs(int nw,int pa,int tid){
dp[nw]+=ptad[nw];
for(int i=0;i<e[nw].size();i++){
    int id=e[nw][i];
    int v=nw^ar[id]^br[id];
    if(v==pa){continue;}
    fdfs(v,nw,id);
    dp[nw]+=dp[v];
}
if(dp[nw]>=K){
    ans.push_back(tid);
}
}
int tv[500005];
bool cmp(int i,int j){
if(rdfn[i]<rdfn[j]){return 1;}return 0;
}
signed main(){
cin>>n>>Q>>K;
for(int i=1;i<=n-1;i++){
    int a;int b;
    cin>>a>>b;
    ar[i]=a;br[i]=b;
    e[a].push_back(i);
    e[b].push_back(i);
}
dfn.push_back(0);
dfs(1,0);
for(int i=1;i<dfn.size();i++){
    if(rdfn[dfn[i]]==0){
        rdfn[dfn[i]]=i;
    }
    rmq[0][i]=dfn[i];
}
for(int i=1;i<=20;i++){
    for(int j=1;j+(1<<i)-1<=dfn.size()-1;j++){
        rmq[i][j]=rmq[i-1][j];
        if(dph[rmq[i][j]]>dph[rmq[i-1][j+(1<<(i-1))]]){
            rmq[i][j]=rmq[i-1][j+(1<<(i-1))];
        }
    }
}
while(Q--){
    int u;
    cin>>u;
    for(int i=1;i<=u;i++){
        cin>>tv[i];
    }
    sort(tv+1,tv+u+1,cmp);
    tv[0]=tv[u];
    for(int i=1;i<=u;i++){
        ptad[tv[i-1]]++;
        ptad[tv[i]]++;
        ptad[lca(tv[i],tv[i-1])]-=2;
    }
}
K+=K;
fdfs(1,0,0);
sort(ans.begin(),ans.end());
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++){
    cout<<ans[i]<<" ";
}


}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:16:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
railway.cpp: In function 'void fdfs(int, int, int)':
railway.cpp:38:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:64:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 | for(int i=1;i<dfn.size();i++){
      |             ~^~~~~~~~~~~
railway.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int j=1;j+(1<<i)-1<=dfn.size()-1;j++){
      |                 ~~~~~~~~~~^~~~~~~~~~~~~~
railway.cpp:96:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 | for(int i=0;i<ans.size();i++){
      |             ~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25