Submission #486275

#TimeUsernameProblemLanguageResultExecution timeMemory
486275kiomiUnique Cities (JOI19_ho_t5)C++17
4 / 100
2056 ms33624 KiB
//#pragma GCC target ("avx2") //#pragma GCC optimization ("Ofast") //#pragma GCC optimization ("unroll-loops") //#pragma comment(linker,"/stack:200000000") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //order_of_key(k): Number of items strictly smaller than k . //find_by_order(k): K-th element in a set (counting from zero). #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define full(x,n) x,x+n+1 #define full(x) x.begin(),x.end() #define finish return 0 #define putb push_back #define f first #define s second //logx(a^n)=loga(a^n)/logx(a) //logx(a*b)=logx(a)+logx(b) //logx(y)=log(y)/log(x) //logb(n)=loga(n)/loga(b) #define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> #define putf push_front #define gainb pop_back //(a+b)^n=sum of C(n,i)*a^i*b^(n-i) 0<=i<=n //(a-b)^n=sum of C(n,i)*a^i*b^(n-i) for even i-for odd i #define gainf pop_front #define len(x) (int)x.size() // 1/b%mod=b^(m-2)%mod // (a>>x)&1==0 // a^b=(a+b)-2(a&b) typedef double db; typedef long long ll; //sum of squares n*(n+1)*(2n+1)/6 //sum of cubes [n*(n+1)/2]^2 //sum of squares for odds n*(4*n*n-1)/3 //sum of cubes for odds n*n*(2*n*n-1) const int ary=1e6+5; const ll mod=1e9+7; const ll inf=1e18; using namespace std; using namespace __gnu_pbds; int n,m,c[ary],e[ary],d[ary],ans; vector<int> g[ary]; set<int> s; void dfs(int v,int pr=0){ e[d[v]]++; for(int i=0;i<len(g[v]);i++){ int to=g[v][i]; if(to==pr){ continue; } d[to]=d[v]+1; dfs(to,v); } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } for(int i=1;i<=n;i++){ cin>>c[i]; } for(int i=1;i<=n;i++){ s.clear(); for(int j=0;j<n;j++){ e[j]=0; } d[i]=0; dfs(i); for(int j=1;j<=n;j++){ if(d[j]&&e[d[j]]==1){ s.insert(c[j]); } } cout<<len(s)<<"\n"; } }

Compilation message (stderr)

joi2019_ho_t5.cpp:15: warning: "full" redefined
   15 | #define full(x) x.begin(),x.end()
      | 
joi2019_ho_t5.cpp:14: note: this is the location of the previous definition
   14 | #define full(x,n) x,x+n+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...