Submission #129909

#TimeUsernameProblemLanguageResultExecution timeMemory
129909Markomafko972Regions (IOI09_regions)C++14
4 / 100
8071 ms131072 KiB
#include <bits/stdc++.h> #define X first #define Y second typedef long long ll; using namespace std; const int MOD = 1e9 + 7; const ll INF = 1e18; int n, r, q, cv, q1, q2; int sq; vector<int> v[200002]; unordered_map<int, ll> m[25002]; int w[200002]; int kol[200002]; int kol2[200002]; vector<int> g[200002]; int t; int d1[200002]; int d2[200002]; void dfs(int x) { for (int i = 0; i < v[x].size(); i ++) { int sus = v[x][i]; dfs(sus); kol[x] += kol[sus]; } //cout << "mapa od " << x << ", " << t << " += " << kol[x] << endl; m[w[x]][t] += kol[x]; } void rek(int x, int y) { y += kol2[x]; m[t][w[x]] += y; for (int i = 0; i < v[x].size(); i ++) { rek(v[x][i], y); } } int tren; void ord(int x) { tren ++; d1[x] = tren; for (int i = 0; i < v[x].size(); i ++) { ord(v[x][i]); } d2[x] = tren; //cout << x << ": " << d1[x] << " " << d2[x] << endl; } int loga[200002]; void update(int x, int y) { for (x; x <= n; x += x & -x) loga[x] += y; } int query(int x) { int out = 0; for (x; x > 0; x -= x & -x) out += loga[x]; return out; } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> r >> q; sq = sqrt(n); cin >> w[1]; g[w[1]].push_back(1); for (int i = 2; i <= n; i ++) { cin >> cv >> w[i]; g[w[i]].push_back(i); v[cv].push_back(i); } ord(1); for (int i = 1; i <= r; i ++) { if (g[i].size() > sq) { memset(kol, 0, sizeof kol); memset(kol2, 0, sizeof kol2); t = i; for (int j = 0; j < g[i].size(); j ++) { kol[g[i][j]] = 1; kol2[g[i][j]] = 1; } dfs(1); rek(1, 0); } } for (int i = 0; i < q; i ++) { cin >> q1 >> q2; if (g[q1].size() > sq && g[q2].size() > sq) { m[q1][q2] /= 2; } if (g[q1].size() <= sq && g[q2].size() <= sq && m[q1][q2] == 0) { for (int j = 0; j < g[q2].size(); j ++) { update(g[q2][j], 1); } for (int j = 0; j < g[q1].size(); j ++) { m[q1][q2] += query(d2[ g[q1][j] ]); m[q1][q2] -= query(d1[ g[q1][j] ]-1); } for (int j = 0; j < g[q2].size(); j ++) { update(g[q2][j], -1); } if (m[q1][q2] == 0) m[q1][q2] = -1; } cout << max(0LL, m[q1][q2]) << endl; } return 0; }

Compilation message (stderr)

regions.cpp: In function 'void dfs(int)':
regions.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v[x].size(); i ++) {
                  ~~^~~~~~~~~~~~~
regions.cpp: In function 'void rek(int, int)':
regions.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v[x].size(); i ++) {
                  ~~^~~~~~~~~~~~~
regions.cpp: In function 'void ord(int)':
regions.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v[x].size(); i ++) {
                  ~~^~~~~~~~~~~~~
regions.cpp: In function 'void update(int, int)':
regions.cpp:55:8: warning: statement has no effect [-Wunused-value]
  for (x; x <= n; x += x & -x) loga[x] += y;
        ^
regions.cpp: In function 'int query(int)':
regions.cpp:60:8: warning: statement has no effect [-Wunused-value]
  for (x; x > 0; x -= x & -x) out += loga[x];
        ^
regions.cpp: In function 'int main()':
regions.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[i].size() > sq) {
       ~~~~~~~~~~~~^~~~
regions.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < g[i].size(); j ++) {
                    ~~^~~~~~~~~~~~~
regions.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() > sq && g[q2].size() > sq) {
       ~~~~~~~~~~~~~^~~~
regions.cpp:97:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() > sq && g[q2].size() > sq) {
                            ~~~~~~~~~~~~~^~~~
regions.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() <= sq && g[q2].size() <= sq && m[q1][q2] == 0) {
       ~~~~~~~~~~~~~^~~~~
regions.cpp:101:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() <= sq && g[q2].size() <= sq && m[q1][q2] == 0) {
                             ~~~~~~~~~~~~~^~~~~
regions.cpp:102:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < g[q2].size(); j ++) {
                    ~~^~~~~~~~~~~~~~
regions.cpp:106:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < g[q1].size(); j ++) {
                    ~~^~~~~~~~~~~~~~
regions.cpp:111:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < g[q2].size(); j ++) {
                    ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...