Submission #1072045

#TimeUsernameProblemLanguageResultExecution timeMemory
1072045aminThe Ties That Guide Us (CEOI23_incursion)C++17
30 / 100
285 ms78556 KiB
#include <vector> #include "incursion.h" #include <cstdio> #include <bits/stdc++.h> using namespace std; int sz[1000000]; int p[1000000]; int vis[1000000]; vector<int>v[1000000]; int n; int centroid; int ans[1000000]; void fin(int in,int col) { vis[in]=1; vector<pair<int,int> >k; if(p[in]!=in) k.push_back({n-sz[in],p[in]}); //cout<<in<<' '<<k.size()<<endl; for(auto i:v[in]) { if(i==p[in]) continue; k.push_back({sz[i],i}); } sort(k.begin(),k.end()); int o=k.size()-1; if(col==1) { for(auto i:k) { if(i.first==k[o].first&&vis[i.second]==0) { int newcol=visit(i.second); fin(i.second,newcol); return ; } } int newcol=visit(k[o].second); fin(k[o].second,newcol); return ; } if(k.size()==1) return ; for(auto i:k) { //cout<<in<<' '<<i.firsti.second<<' '<<k.size()<<endl; if(i.first==k[0].first&&vis[i.second]==0) { int newcol=visit(i.second); fin(i.second,newcol); return ; } } } void dfs(int in,int par) { sz[in]=1; p[in]=par; for(auto i:v[in]) { if(i==par) continue; dfs(i,in); sz[in]+=sz[i]; } if(in==par) { ans[in]=0; //return ; }else { int h=1; int j=n-sz[in]; for(auto i:v[in]) { if(i==par) continue; if(sz[i]>j) h=0; } ans[in]=h; //cout<<in<<' '<<ans[in]<<endl; } } vector<int> mark(vector<pair<int, int>> f, int safe) { n=f.size()+1; vector<int>u; for(int i=0;i<n-1;i++) { v[f[i].first].push_back(f[i].second); v[f[i].second].push_back(f[i].first); } dfs(safe,safe); for(int i=1;i<=n;i++) { u.push_back(ans[i]); } return u; } void locate(vector<pair<int, int>> f, int curr, int t) { n=f.size()+1; for(int i=0;i<n;i++) { v[i].clear(); } for(int i=0;i<n-1;i++) { v[f[i].first].push_back(f[i].second); v[f[i].second].push_back(f[i].first); } dfs(curr,curr); fin(curr,t); return ; }

Compilation message (stderr)

interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...