제출 #523513

#제출 시각아이디문제언어결과실행 시간메모리
523513Vladth11Regions (IOI09_regions)C++14
13 / 100
1781 ms50148 KiB
#include <bits/stdc++.h> #define debug(x) cerr << #x << " " << x << "\n" #define debugs(x) cerr << #x << " " << x << " " using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <long double, pii> muchie; const int NMAX = 200001; const int VMAX = 21; const int INF = (1LL << 60); const int MOD = 1000000007; const int BLOCK = 700; const int base = 31; const int nr_of_bits = 21; const int MMAX = NMAX / BLOCK + 2; vector <int> v[NMAX], vertices[NMAX]; vector <pii> lista[NMAX]; int stamp; int n, R, Q; ll sol[MMAX][25001]; ll precalc[25001][MMAX]; int region[NMAX]; int bigR[NMAX]; int smallR[NMAX]; int bigIdx[NMAX]; int smallIdx[NMAX]; int cati[NMAX]; int stiva[NMAX]; int vf; int countAbove[MMAX]; int timestamp; pii timp[NMAX]; int preorder[NMAX + 1]; void DFS(int node, int p) { stamp++; timp[node].first = ++timestamp; lista[region[node]].push_back({node, stamp}); if(bigIdx[region[node]] != 0) { countAbove[bigIdx[region[node]]]++; } for(int i = 1; i <= R; i++) { sol[i][region[node]] += 1LL * countAbove[i]; } for(auto x : v[node]) { if(x == p) continue; DFS(x, node); } if(bigIdx[region[node]] != 0) { countAbove[bigIdx[region[node]]]--; } stamp++; timp[node].second = timestamp; lista[region[node]].push_back({node, stamp}); } int main() { int i; cin >> n >> R >> Q; cin >> region[1]; vertices[region[1]].push_back(1); cati[region[1]]++; for(i = 2; i <= n; i++) { int p; cin >> p >> region[i]; v[p].push_back(i); v[i].push_back(p); vertices[region[i]].push_back(i); cati[region[i]]++; } int cc = 0, sc = 0; for(i = 1; i <= R; i++) { if(cati[i] >= BLOCK) { bigR[++cc] = i; bigIdx[i] = cc; } else { smallR[++sc] = i; smallIdx[i] = sc; } } DFS(1, 0); for(int i = 1; i <= R; i++) { if(bigIdx[i] == 0) continue; for(auto x : vertices[i]) { preorder[timp[x].first]++; /// BRUH preorder[timp[x].second + 1]--; } for(int j = 1; j <= n; j++) { preorder[j] += preorder[j - 1]; } for(int j = 1; j <= sc; j++) { for(auto x : vertices[smallR[j]]) precalc[j][bigIdx[i]] += 1LL * (preorder[timp[x].second] - preorder[timp[x].first - 1]); } for(int j = 1; j <= n; j++) preorder[j] = 0; } while(Q--) { int a, b; cin >> a >> b; if(bigIdx[a] != 0) { /// Aia de sus mare cout << sol[bigIdx[a]][b] << "\n"; } else if(bigIdx[b] != 0) { /// Aia de jos mare si aia de sus mica cout << precalc[smallIdx[a]][bigIdx[b]] << "\n"; } else { /// Ambele mici int i = 0; int j = 0; int deschise = 0; vf = 0; int rez = 0; while(i < lista[a].size() && j < lista[b].size()) { pii x = lista[a][i]; pii y = lista[b][j]; if(x.second < y.second) { if(stiva[vf] == x.first) { vf--; deschise--; } else { stiva[++vf] = x.first; deschise++; } i++; } else { if(stiva[vf] == y.first) { vf--; } else { rez += deschise; stiva[++vf] = y.first; } j++; } } cout << rez; } cout << endl; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

regions.cpp:12:22: warning: overflow in conversion from 'long long int' to 'int' changes value from '1152921504606846976' to '0' [-Woverflow]
   12 | const int INF = (1LL << 60);
      |                 ~~~~~^~~~~~
regions.cpp: In function 'int main()':
regions.cpp:115:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             while(i < lista[a].size() && j < lista[b].size()) {
      |                   ~~^~~~~~~~~~~~~~~~~
regions.cpp:115:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             while(i < lista[a].size() && j < lista[b].size()) {
      |                                          ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...