Submission #783525

#	Time	Username	Problem	Language	Result	Execution time	Memory
783525		1075508020060209tc	Railway (BOI17_railway)	C++14	100 / 100	191 ms	103104 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;
}
set<int>del[500005];
set<int>ptad[500005];
vector<int>ans;
int dp[500005];
void fdfs(int nw,int pa,int tid){

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);
    if(ptad[v].size()>ptad[nw].size()){
        swap(ptad[v],ptad[nw]);
    }
    /*
    for(auto it=ptad[v].begin();it!=ptad[v].end();it++){
        ptad[nw].insert(*it);
    }*/
}

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;}
    for(auto it=ptad[v].begin();it!=ptad[v].end();it++){
        ptad[nw].insert(*it);
    }
}
for(auto it=del[nw].begin();it!=del[nw].end();it++){
    ptad[nw].erase(*it);
}

if(ptad[nw].size()>=K){
    ans.push_back(tid);
}
}

signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);

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;
    int a;int b;
    vector<int>vc;
    for(int i=1;i<=u;i++){
        int v;
        cin>>v;
        vc.push_back(v);
        ptad[v].insert(Q);
    }
    int lc=vc[0];
    for(int i=1;i<vc.size();i++){
        lc=lca(lc,vc[i]);
    }
    del[lc].insert(Q);
}
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:39:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
railway.cpp:53:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
railway.cpp:65:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 | if(ptad[nw].size()>=K){
      |    ~~~~~~~~~~~~~~~^~~
railway.cpp: In function 'int main()':
railway.cpp:84:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 | for(int i=1;i<dfn.size();i++){
      |             ~^~~~~~~~~~~
railway.cpp:91:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int j=1;j+(1<<i)-1<=dfn.size()-1;j++){
      |                 ~~~~~~~~~~^~~~~~~~~~~~~~
railway.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i=1;i<vc.size();i++){
      |                 ~^~~~~~~~~~
railway.cpp:101:9: warning: unused variable 'a' [-Wunused-variable]
  101 |     int a;int b;
      |         ^
railway.cpp:101:15: warning: unused variable 'b' [-Wunused-variable]
  101 |     int a;int b;
      |               ^
railway.cpp:118:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 | 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