oj.uz

Submission #311354

# Submission time Handle Problem Language Result Execution time Memory
311354 2020-10-10T01:04:29 Z caoash Regions (IOI09_regions) C++14
30 / 100
 5232 ms 131076 KB 
#include <bits/stdc++.h> 
using namespace std;

using ll = long long;

using vi = vector<int>;
using vl = vector<ll>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

const int MX = 200005;
const int MOD = (int) (1e9 + 7);
const ll INF = (ll) 1e18;

namespace output {
  void pr(int x) {
    cout << x;
  }
  void pr(long x) {
    cout << x;
  }
  void pr(ll x) {
    cout << x;
  }
  void pr(unsigned x) {
    cout << x;
  }
  void pr(unsigned long x) {
    cout << x;
  }
  void pr(unsigned long long x) {
    cout << x;
  }
  void pr(float x) {
    cout << x;
  }
  void pr(double x) {
    cout << x;
  }
  void pr(long double x) {
    cout << x;
  }
  void pr(char x) {
    cout << x;
  }
  void pr(const char * x) {
    cout << x;
  }
  void pr(const string & x) {
    cout << x;
  }
  void pr(bool x) {
    pr(x ? "true" : "false");
  }

  template < class T1, class T2 > void pr(const pair < T1, T2 > & x);
  template < class T > void pr(const T & x);

  template < class T, class...Ts > void pr(const T & t,
    const Ts & ...ts) {
    pr(t);
    pr(ts...);
  }
  template < class T1, class T2 > void pr(const pair < T1, T2 > & x) {
    pr("{", x.f, ", ", x.s, "}");
  }
  template < class T > void pr(const T & x) {
    pr("{"); // const iterator needed for vector<bool>
    bool fst = 1;
    for (const auto & a: x) pr(!fst ? ", " : "", a), fst = 0;
    pr("}");
  }

  void ps() {
    pr("\n");
  } // print w/ spaces
  template < class T, class...Ts > void ps(const T & t,
    const Ts & ...ts) {
    pr(t);
    if (sizeof...(ts)) pr(" ");
    ps(ts...);
  }

  void pc() {
    cout << "]" << endl;
  } // debug w/ commas
  template < class T, class...Ts > void pc(const T & t,
    const Ts & ...ts) {
    pr(t);
    if (sizeof...(ts)) pr(", ");
    pc(ts...);
  }
  #define dbg(x...) pr("[", #x, "] = ["), pc(x);
}

#ifdef LOCAL
using namespace output;
#endif

vi adj[MX];
int nr[MX];
int p[MX];
map<pi, int> ans;
map<int, int> vals[MX];

void mrg(map<int, int> &v1, map<int, int> &v2) {
    for (auto x : v2) v1[x.f] += x.s;
    v2.clear();
}

void dfs(int v, int p) {
    vals[v][nr[v]]++; 
    for (int to : adj[v]) {
        if (to != p) {
            dfs(to, v);
            mrg(vals[v], vals[to]);
        }
    }
    for (auto x : vals[v]) ans[mp(nr[v], x.f)] += x.s;
    // dbg(v, vals[v]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, r, q; cin >> n >> r >> q;
    cin >> nr[0];
    for (int i = 1; i < n; i++) cin >> p[i] >> nr[i];
    for (int i = 1; i < n; i++) {
        // dbg(i, p[i]);
        // dbg(p[i] - 1, i);
        adj[p[i] - 1].pb(i);
    }
    dfs(0, -1);
    for (int i = 0; i < q; i++) {
        int qu, qv; cin >> qu >> qv;
        cout << ans[mp(qu, qv)] << endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 11 ms 14464 KB Output is correct
3 Correct 12 ms 14464 KB Output is correct
4 Correct 15 ms 14464 KB Output is correct
5 Correct 16 ms 14592 KB Output is correct
6 Correct 66 ms 17784 KB Output is correct
7 Correct 48 ms 15488 KB Output is correct
8 Correct 60 ms 16632 KB Output is correct
9 Correct 386 ms 21116 KB Output is correct
10 Correct 175 ms 22904 KB Output is correct
11 Correct 274 ms 19832 KB Output is correct
12 Correct 1363 ms 28792 KB Output is correct
13 Correct 165 ms 20080 KB Output is correct
14 Correct 270 ms 18168 KB Output is correct
15 Correct 2144 ms 25888 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2597 ms 22392 KB Output is correct
2 Correct 1326 ms 20216 KB Output is correct
3 Correct 5232 ms 27772 KB Output is correct
4 Runtime error 1243 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 1524 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 1302 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 917 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 1652 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 994 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 1514 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 1029 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 1347 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 1267 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 1205 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 1091 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 889 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 1147 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)