Submission #942055

#TimeUsernameProblemLanguageResultExecution timeMemory
942055dshfjkaRailway (BOI17_railway)C++14
0 / 100
114 ms50792 KiB
#include <bits/stdc++.h> #define LL long long #define fi first #define se second #define mp make_pair using namespace std; const LL N=1e5; LL arr[N+5],res; vector<LL>dep[N+5],akhir; LL n,m,k; vector<pair<LL,LL>>adj[N+5]; bool visited[N+5]; struct disjoint_set{ LL parent[N+5],sz[N+5],ans[N+5]; bool vis[N+5]; map<LL,LL>mp[N+5]; disjoint_set(){ for(LL a=1;a<=N;a++)parent[a]=a; for(LL a=1;a<=N;a++)sz[a]=1; } LL root(LL x) { // printf("x=%lld\n"); if(parent[x]==x)return x; return parent[x]=root(parent[x]); } void merge(LL x, LL y) { // printf("MERGE(%lld, %lld)\n",x,y); LL px=root(x),py=root(y); // printf("%lld %lld\n",px,py); if(px==py)return; // printf("HEE\n"); if(sz[px]<sz[py])swap(px,py); sz[px]+=sz[py]; parent[py]=px; // printf("DOR\n"); for(pair<LL,LL> a:mp[py]) { // printf("%lld %lld %lld\n",py,a.fi,a.se); // printf("dep[%lld][%lld]=%lld\n",px,a.fi,mp[px][a.fi]); if(!mp[px][a.fi]) { ans[px]++; } mp[px][a.fi]+=a.se; if(mp[px][a.fi]==arr[a.fi])ans[px]--; } } }dsu; void dfs(LL x, LL num) { // printf("%lld %lld\n",x,num); visited[x]=1; for(LL a:dep[x]){ dsu.mp[x][a]++; dsu.ans[x]++; } for(pair<LL,LL> a:adj[x]) { if(visited[a.fi])continue; dfs(a.fi,a.se); dsu.merge(a.fi,x); } // printf("%lld %lld , dsu.ans[%lld]=%lld\n",x,num, dsu.root(x),dsu.ans[dsu.root(x)]); // printf("%lld : %lld\n",num,dsu.ans[dsu.root(x)]); if(dsu.ans[dsu.root(x)]>=k){ akhir.push_back(num); } } int main() { scanf("%lld %lld %lld",&n,&m,&k); for(LL a=1;a<n;a++) { LL x,y; scanf("%lld %lld",&x,&y); adj[x].push_back(mp(y,a)); adj[y].push_back(mp(x,a)); } for(LL a=1;a<=m;a++) { scanf("%lld",&arr[a]); for(LL b=1;b<=arr[a];b++) { LL x; scanf("%lld",&x); dep[x].push_back(a); } } dfs(1,0); // printf("SINI\n"); printf("%lld\n",akhir.size()); for(LL x:akhir){ printf("%lld ",x); } }

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:95:13: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   95 |  printf("%lld\n",akhir.size());
      |          ~~~^    ~~~~~~~~~~~~
      |             |              |
      |             long long int  std::vector<long long int>::size_type {aka long unsigned int}
      |          %ld
railway.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%lld %lld %lld",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%lld %lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
railway.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%lld",&arr[a]);
      |   ~~~~~^~~~~~~~~~~~~~~~
railway.cpp:89:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |    scanf("%lld",&x);
      |    ~~~~~^~~~~~~~~~~
#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...