oj.uz

답안 #311357

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
311357 2020-10-10T01:07:48 Z caoash Regions (IOI09_regions) C++14
8 / 100
 8000 ms 61412 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

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
};

vi adj[MX];
int nr[MX];
int p[MX];
gp_hash_table<pi, int, hash_pair> 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
8.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 12 ms 14464 KB Output is correct
4 Correct 16 ms 14464 KB Output is correct
5 Correct 33 ms 14592 KB Output is correct
6 Correct 5137 ms 17988 KB Output is correct
7 Correct 413 ms 15476 KB Output is correct
8 Correct 1748 ms 16244 KB Output is correct
9 Execution timed out 8057 ms 22084 KB Time limit exceeded
10 Execution timed out 8054 ms 21380 KB Time limit exceeded
11 Execution timed out 8041 ms 21776 KB Time limit exceeded
12 Execution timed out 8039 ms 22264 KB Time limit exceeded
13 Execution timed out 8042 ms 21768 KB Time limit exceeded
14 Execution timed out 8032 ms 18944 KB Time limit exceeded
15 Execution timed out 8021 ms 26276 KB Time limit exceeded

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8013 ms 21336 KB Time limit exceeded
2 Execution timed out 8032 ms 20096 KB Time limit exceeded
3 Execution timed out 8019 ms 25576 KB Time limit exceeded
4 Execution timed out 8023 ms 21996 KB Time limit exceeded
5 Execution timed out 8064 ms 22916 KB Time limit exceeded
6 Execution timed out 8035 ms 22784 KB Time limit exceeded
7 Execution timed out 8055 ms 23276 KB Time limit exceeded
8 Execution timed out 8035 ms 27228 KB Time limit exceeded
9 Execution timed out 8007 ms 26480 KB Time limit exceeded
10 Execution timed out 8045 ms 28652 KB Time limit exceeded
11 Execution timed out 8036 ms 25976 KB Time limit exceeded
12 Execution timed out 8053 ms 28208 KB Time limit exceeded
13 Execution timed out 8092 ms 28004 KB Time limit exceeded
14 Execution timed out 8021 ms 27780 KB Time limit exceeded
15 Execution timed out 8007 ms 35444 KB Time limit exceeded
16 Execution timed out 8031 ms 61412 KB Time limit exceeded
17 Execution timed out 8095 ms 29592 KB Time limit exceeded