Submission #492115

#TimeUsernameProblemLanguageResultExecution timeMemory
492115lukameladzeRegions (IOI09_regions)C++14
95 / 100
6012 ms131076 KiB
# include <bits/stdc++.h> #define f first #define s second #define pb push_back #define pii pair <int, int> using namespace std; const int N = 2e5 + 5, B = 400; int tin,in[N],out[N],r1,r2,fer,n,le,ri,up,hea[N],lig[N],col[N],r,q,p[N],idx[N]; multiset <pii> :: iterator it; int mpp[N]; map <int,int>ans[N]; vector <int> heavy,light; vector <int> v[N],v1[N]; multiset <pii> ms[N]; vector <pii> vv; multiset <int> mss; void dfs(int a, int p) { tin++; in[a] = tin; vv.pb({in[a],a}); for (int i = 0; i < v[a].size(); i++) { int to = v[a][i]; if (to == p) continue; dfs(to,a); } out[a] = tin; } void dfs1(int a, int p) { if (hea[col[a]]) { mpp[col[a]]++; } for (int j = 0; j < heavy.size(); j++) { fer = heavy[j]; //if (fer == 1 && col[a] == 3) //cout<<fer<<" "<<a<<" "<<col[a]<<endl; if (mpp[fer]) ans[fer][col[a]]+= mpp[fer]; } for (int i = 0; i < v[a].size(); i++) { int to = v[a][i]; if (to == p) continue; dfs1(to,a); } if (hea[col[a]]) mpp[col[a]]--; } main() { cin>>n>>r>>q; for (int i = 1; i <= n; i++) { if (i != 1) cin>>p[i],v[p[i]].pb(i),v[i].pb(p[i]); cin>>col[i]; v1[col[i]].pb(i); } for (int i = 1; i <= r; i++) { if (v1[i].size() >= B) heavy.pb(i), hea[i] = 1; else light.pb(i),lig[i] = 1; } dfs(1,0); sort(vv.begin(),vv.end()); for (int i = 0; i < vv.size(); i++) { // if (!hea[col[vv[i].s]]) continue; idx[col[vv[i].s]]++; // cout<<vv[i].s<<" "<<vv[i].f<<" "<<col[vv[i].s]<<" "<<idx[col[vv[i].s]]<<endl; ms[col[vv[i].s]].insert({vv[i].f,idx[col[vv[i].s]]}); } //ins[feri].insert({ini, meramdenea}); /* for (int i = 1; i <= r; i++) { coll = i; for (int j = 0; j < v1[coll].size(); j++) { ins[coll].pb(in[v1[coll][j]]); } }*/ dfs1(1,0); while(q--) { cin>>r1>>r2; if (lig[r1]) { int anss = 0; for (int i = 0; i < v1[r1].size(); i++) { up = v1[r1][i]; // cout<<up<<"s"<<endl; it = ms[r2].lower_bound({in[up],0}); if (it == ms[r2].end()) continue; // cout<<r2<<" "<<(*it).s<<endl; le = (*it).s; it = ms[r2].upper_bound({out[up],1e9}); if (it == ms[r2].end()) ri = ms[r2].size(); else ri = (*it).s - 1; anss += (ri - le + 1); } cout<<anss<<endl; continue; } cout<<ans[r1][r2]<<endl; } }

Compilation message (stderr)

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
regions.cpp: In function 'void dfs1(int, int)':
regions.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int j = 0; j < heavy.size(); j++) {
      |                     ~~^~~~~~~~~~~~~~
regions.cpp:38:23: 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 < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main() {
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < vv.size(); i++) {
      |                     ~~^~~~~~~~~~~
regions.cpp:78:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for (int i = 0; i < v1[r1].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...