oj.uz

Submission #311371

# Submission time Handle Problem Language Result Execution time Memory
311371 2020-10-10T02:42:10 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] = 0; 
        else good[i] = 1;
    }
    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 10 ms 15104 KB Output is correct
2 Correct 10 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 20 ms 15232 KB Output is correct
6 Correct 71 ms 18424 KB Output is correct
7 Correct 82 ms 16632 KB Output is correct
8 Correct 124 ms 17660 KB Output is correct
9 Correct 463 ms 21496 KB Output is correct
10 Correct 1856 ms 26744 KB Output is correct
11 Correct 1196 ms 20604 KB Output is correct
12 Correct 4198 ms 29376 KB Output is correct
13 Correct 2853 ms 23296 KB Output is correct
14 Correct 1583 ms 19248 KB Output is correct
15 Correct 2627 ms 25512 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 4871 ms 23348 KB Output isn't correct
2 Incorrect 5724 ms 21928 KB Output isn't correct
3 Execution timed out 8026 ms 28068 KB Time limit exceeded
4 Runtime error 3882 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 5127 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 3506 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 2399 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 4260 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 2701 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 4078 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 3550 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 4623 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Execution timed out 8060 ms 129896 KB Time limit exceeded
14 Execution timed out 8098 ms 94560 KB Time limit exceeded
15 Execution timed out 8031 ms 38164 KB Time limit exceeded
16 Execution timed out 8031 ms 54708 KB Time limit exceeded
17 Execution timed out 8035 ms 62504 KB Time limit exceeded