제출 #472331

#제출 시각아이디문제언어결과실행 시간메모리
472331fadi57Railway (BOI17_railway)C++14
0 / 100
75 ms24624 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; const int mx=1e5+5; typedef long long ll; int mod=1e9+7; const int MXm=22; #define F first #define S second const int inf=1e9+10; int aa[mx]; vector<int>adj[mx]; vector<pair<int,int>>edges; int depth[mx]; int dp[20][mx]; int dp2[mx]; vector<int>a[mx] ; void dfs(int node,int par){ dp[0][node]=par; for(int j=1;j<19;j++){ dp[j][node]=dp[j-1][dp[j-1][node]]; } for(auto it:adj[node]){ if(it==par){continue;} depth[it]=depth[node]+1; dfs(it,node); } return; } int kth(int node,int x){ for(int i=0;i<19;i++){ if(x&(1<<i)){ x-=(1<<i); node=dp[i][node]; } } return node; } int lca(int a,int b){ if(depth[b]<depth[a]){swap(a,b);} int dis=depth[b]-depth[a]; b=kth(b,dis); // cout<<b; if(a==b){return a;} for(int j=19;j>=0;j--){ int aa=dp[j][a];int bb=dp[j][b]; if(aa==bb){continue;} a=aa;b=bb; } return dp[0][a]; } int n,m,k; map<pair<int,int>,int>mp; int dfs2(int node,int par){ int sum2=0; for(auto it:adj[node]){ if(it==par){continue;} int z= dfs2(it,node); if(z>0){ int x=min(node,it);int y=max(node,it); mp[{x,y}]+=z; } sum2+=z; } dp2[node]+=sum2; //cout<<node<<" "<<dp2[node]<<endl; return dp2[node]; } void test(){ for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(mp[{i,j}]){ cout<<i<<" "<<j<<endl; } } } } void test2(){ vector<int>ans; int anss=0; for(int i=0;i<n;i++){ if(mp[{edges[i].first,edges[i].second}]>=k){ anss++; ans.push_back(i+1); } } cout<<anss<<endl; for(auto it:ans){ cout<<it<<" "; } } void solve(){ for(int i=0;i<m;i++){ int me=lca(a[i][0],a[i][1]); dp2[me]-=2; dp2[a[i][0]]++; dp2[a[i][1]]++; } dfs2(1,0); } void solve2(){ for(int i=0;i<m;i++){ for(int j=0;j<a[i].size();j++){ for(int jj=j+1;jj<a[i].size();jj++){ int me=lca(a[i][j],a[i][jj]); dp2[me]-=2; dp2[a[i][j]]++; dp2[a[i][jj]]++; // cout<<me<<endl; } } dfs2(1,0); } } int main(){ ios_base::sync_with_stdio(0) ; cin.tie(0) ; cin>>n>>m>>k; for(int i=0;i<n-1;i++){ int a,b;cin>>a>>b; if(b<a){swap(a,b);} edges.push_back({a,b}); adj[a].push_back(b); adj[b].push_back(a); } int leaf1=0;int leaf2=0; dfs(1,0); int ok=0; int ok2=1; for(int i=0;i<m;i++){ int s;cin>>s; for(int j=0;j<s;j++){ int x;cin>>x; a[i].push_back(x); } if(k==m&&s==2){ }else{ ok=0; } // test(); //mp.clear(); // cout<<"test \n"; } if(ok){ solve(); }else{ // solve2(); } //test2(); /* cout<<dp[1][6]; lca(6,5); */ }

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp: In function 'void solve2()':
railway.cpp:138:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |                for(int j=0;j<a[i].size();j++){
      |                            ~^~~~~~~~~~~~
railway.cpp:139:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |                for(int jj=j+1;jj<a[i].size();jj++){
      |                               ~~^~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:173:11: warning: unused variable 'leaf1' [-Wunused-variable]
  173 |       int leaf1=0;int leaf2=0;
      |           ^~~~~
railway.cpp:173:23: warning: unused variable 'leaf2' [-Wunused-variable]
  173 |       int leaf1=0;int leaf2=0;
      |                       ^~~~~
railway.cpp:175:21: warning: unused variable 'ok2' [-Wunused-variable]
  175 |       int ok=0; int ok2=1;
      |                     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...