oj.uz

답안 #311382

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
311382 2020-10-10T03:39:28 Z caoash Regions (IOI09_regions) C++14
80 / 100
 7455 ms 131072 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[x.f] += x.s;
    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]);
        }
    }
    // assert(sz(vals[v]) <= B);
    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;
    }
    if (good[nr[v]]) curr[nr[v]]++;
    // assert(sz(curr) <= B);
    for (int to : adj[v]) {
        if (to != p) {
            dfs_path(to, v, curr);
        }
    }
    if (good[nr[v]]) {
        curr[nr[v]]--;
        if (curr[nr[v]] == 0) curr.erase(nr[v]);
    }
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15104 KB Output is correct
2 Correct 10 ms 15104 KB Output is correct
3 Correct 11 ms 15104 KB Output is correct
4 Correct 14 ms 15104 KB Output is correct
5 Correct 17 ms 15104 KB Output is correct
6 Correct 27 ms 15232 KB Output is correct
7 Correct 40 ms 15104 KB Output is correct
8 Correct 43 ms 15232 KB Output is correct
9 Correct 64 ms 16000 KB Output is correct
10 Correct 107 ms 15616 KB Output is correct
11 Correct 160 ms 15904 KB Output is correct
12 Correct 179 ms 16896 KB Output is correct
13 Correct 244 ms 16128 KB Output is correct
14 Correct 391 ms 16640 KB Output is correct
15 Correct 459 ms 22400 KB Output is correct

Subtask #2
65.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1710 ms 21496 KB Output is correct
2 Correct 1933 ms 19248 KB Output is correct
3 Correct 3538 ms 25468 KB Output is correct
4 Correct 421 ms 16888 KB Output is correct
5 Correct 436 ms 20344 KB Output is correct
6 Correct 1948 ms 18424 KB Output is correct
7 Correct 2643 ms 19364 KB Output is correct
8 Correct 2580 ms 29436 KB Output is correct
9 Correct 4284 ms 25976 KB Output is correct
10 Correct 7182 ms 36472 KB Output is correct
11 Correct 7455 ms 24568 KB Output is correct
12 Runtime error 335 ms 60396 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 259 ms 62968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 1950 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 433 ms 84576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Correct 5457 ms 56784 KB Output is correct
17 Correct 6848 ms 97272 KB Output is correct