제출 #783166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
783166		1075508020060209tc	Railway (BOI17_railway)	C++14	29 / 100	143 ms	42392 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);
}
}

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;
    int a;int b;
    cin>>a>>b;
    ptad[a]++;
    ptad[b]++;
    ptad[lca(a,b)]-=2;
}
fdfs(1,0,0);
sort(ans.begin(),ans.end());
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++){
    cout<<ans[i]<<" ";
}


}

컴파일 시 표준 에러 (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:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 | for(int i=1;i<dfn.size();i++){
      |             ~^~~~~~~~~~~
railway.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int j=1;j+(1<<i)-1<=dfn.size()-1;j++){
      |                 ~~~~~~~~~~^~~~~~~~~~~~~~
railway.cpp:87:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 | for(int i=0;i<ans.size();i++){
      |             ~^~~~~~~~~~~

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