oj.uz

Submission #311372

# Submission time Handle Problem Language Result Execution time Memory
311372 2020-10-10T02:45:58 Z caoash Regions (IOI09_regions) C++14
15 / 100
 8000 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

template <class T, int ...Ns> struct BIT {
	T val = 0; void upd(T v) { val += v; }
	T query() { return val; }
};
template <class T, int N, int... Ns> struct BIT<T, N, Ns...> {
	BIT<T,Ns...> bit[N+1];
	template<typename... Args> void upd(int pos, Args... args) { assert(pos > 0);
		for (; pos<=N; pos+=pos&-pos) bit[pos].upd(args...); }
	template<typename... Args> T sum(int r, Args... args) {
		T res=0; for (;r;r-=r&-r) res += bit[r].query(args...); 
		return res; }
	template<typename... Args> T query(int l, int r, Args... 
		args) { return sum(r,args...)-sum(l-1,args...); }
}; 

const int B = 500;
const int MXR = 25005;

vi adj[MX];
int nr[MX], p[MX], good[MXR], st[MX], sz[MX];
int cnt = 0;
BIT<int, MX> orz;
vi locs[MXR];
map<int, int> vals[MX];
map<pi, int> pre;

void dfs_init(int v, int p) {
    st[v] = cnt++;
    sz[v] = 1;
    for (int to : adj[v]) {
        if (to != p) {
            dfs_init(to, v);
            sz[v] += sz[to];
        }
    }
}

void comb(map<int, int> &a, map<int, int> &b) {
    if (sz(a) < sz(b)) swap(a, b);
    for (auto x : b) a.insert(x);
    b.clear();
}

void dfs_merge(int v, int p) {
    if (good[nr[v]]) vals[v][nr[v]]++;
    for (int to : adj[v]) {
        if (to != p) {
            dfs_merge(to, v);
            comb(vals[v], vals[to]);
        }
    }
    if (!good[nr[v]]) {
        for (auto x : vals[v]) {
            pre[mp(nr[v], x.f)] += x.s;
        }
    }
}

void dfs_path(int v, int p, map<int, int> &curr) {
    for (auto x : curr) {
        pre[mp(x.f, nr[v])] += x.s;
    }
    for (int to : adj[v]) {
        if (to != p) {
            curr[nr[to]]++;
            dfs_path(to, v, curr);
            curr[nr[to]]--;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, r, q; cin >> n >> r >> q;
    for (int i = 0; i < n; i++) {
        if (i) {
            cin >> p[i];
            p[i]--;
        }
        cin >> nr[i];
        nr[i]--;
        good[nr[i]]++;
        locs[nr[i]].pb(i);
    }
    for (int i = 1; i < n; i++) {
        adj[p[i]].pb(i);
    }
    for (int i = 0; i < r; i++) {
        if (good[i] > B) good[i] = 1; 
        else good[i] = 0;
    }
    dfs_init(0, -1);
    dfs_merge(0, -1);
    map<int, int> init;
    dfs_path(0, -1, init);
    for (int i = 0; i < q; i++) {
        int qu, qv; cin >> qu >> qv;
        qu--, qv--;
        if (!good[qu] && !good[qv]) {
            int ret = 0;
            for (auto p : locs[qv]) {
                orz.upd(st[p] + 1, 1);
                // dbg(st[p], 1);
            }
            for (auto p : locs[qu]) {
                ret += orz.query(st[p] + 1, st[p] + sz[p]);
                // dbg(st[p], st[p] + sz[p] - 1);
            }
            for (auto p : locs[qv]) {
                orz.upd(st[p] + 1, -1);
                // dbg(st[p], -1);
            }
            cout << ret << endl;
        } else {
            assert(pre.find(mp(qu, qv)) != pre.end());
            cout << pre[mp(qu, qv)] << endl;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15104 KB Output is correct
2 Correct 11 ms 15104 KB Output is correct
3 Correct 13 ms 15104 KB Output is correct
4 Correct 16 ms 15104 KB Output is correct
5 Correct 21 ms 15232 KB Output is correct
6 Correct 54 ms 18424 KB Output is correct
7 Correct 80 ms 16512 KB Output is correct
8 Correct 119 ms 17656 KB Output is correct
9 Correct 443 ms 21624 KB Output is correct
10 Correct 1729 ms 27128 KB Output is correct
11 Correct 1106 ms 20472 KB Output is correct
12 Correct 3833 ms 29432 KB Output is correct
13 Correct 2651 ms 23656 KB Output is correct
14 Correct 1632 ms 19232 KB Output is correct
15 Correct 2499 ms 25468 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 4157 ms 23420 KB Output isn't correct
2 Incorrect 5006 ms 21912 KB Output isn't correct
3 Execution timed out 8061 ms 28152 KB Time limit exceeded
4 Runtime error 3786 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 4918 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 3409 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 2441 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 4163 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 2766 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 4135 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 3565 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 3486 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 3450 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 3170 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 2610 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 2398 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 2353 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)