oj.uz

Submission #311355

# Submission time Handle Problem Language Result Execution time Memory
311355 2020-10-10T01:05:40 Z caoash Regions (IOI09_regions) C++14
30 / 100
 2978 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) {
    if (sz(v1) < sz(v2)) swap(v1, 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 10 ms 14464 KB Output is correct
3 Correct 12 ms 14484 KB Output is correct
4 Correct 14 ms 14464 KB Output is correct
5 Correct 17 ms 14592 KB Output is correct
6 Correct 48 ms 17784 KB Output is correct
7 Correct 43 ms 15488 KB Output is correct
8 Correct 57 ms 16632 KB Output is correct
9 Correct 211 ms 20988 KB Output is correct
10 Correct 152 ms 22744 KB Output is correct
11 Correct 206 ms 19848 KB Output is correct
12 Correct 741 ms 28792 KB Output is correct
13 Correct 195 ms 20088 KB Output is correct
14 Correct 200 ms 18336 KB Output is correct
15 Correct 1112 ms 25976 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1644 ms 22396 KB Output is correct
2 Correct 1120 ms 20088 KB Output is correct
3 Correct 2978 ms 27768 KB Output is correct
4 Runtime error 753 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 824 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 792 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 609 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 881 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 584 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 882 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 671 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 885 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 770 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 788 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 650 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 542 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 688 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)