oj.uz

Submission #311375

# Submission time Handle Problem Language Result Execution time Memory
311375 2020-10-10T02:55:02 Z caoash Regions (IOI09_regions) C++14
0 / 100
 2128 ms 93816 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]);
        }
    }
    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) {
    assert(sz(curr) <= B);
    for (auto x : curr) {
        pre[mp(x.f, nr[v])] += x.s;
    }
    for (int to : adj[v]) {
        if (to != p) {
            if (good[nr[to]]) curr[nr[to]]++;
            dfs_path(to, v, curr);
            if (good[nr[to]]) 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;
            */
            cout << -1 << '\n';
        } else {
            assert(pre.find(mp(qu, qv)) != pre.end());
            cout << pre[mp(qu, qv)] << endl;
        }
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9 ms 14976 KB Time limit exceeded (wall clock)
2 Execution timed out 9 ms 14976 KB Time limit exceeded (wall clock)
3 Execution timed out 9 ms 14976 KB Time limit exceeded (wall clock)
4 Execution timed out 10 ms 14976 KB Time limit exceeded (wall clock)
5 Execution timed out 10 ms 15056 KB Time limit exceeded (wall clock)
6 Execution timed out 9 ms 15104 KB Time limit exceeded (wall clock)
7 Execution timed out 9 ms 15104 KB Time limit exceeded (wall clock)
8 Execution timed out 10 ms 15104 KB Time limit exceeded (wall clock)
9 Execution timed out 11 ms 15872 KB Time limit exceeded (wall clock)
10 Execution timed out 13 ms 15488 KB Time limit exceeded (wall clock)
11 Execution timed out 14 ms 15872 KB Time limit exceeded (wall clock)
12 Execution timed out 16 ms 16640 KB Time limit exceeded (wall clock)
13 Execution timed out 18 ms 16000 KB Time limit exceeded (wall clock)
14 Execution timed out 23 ms 16512 KB Time limit exceeded (wall clock)
15 Execution timed out 24 ms 21496 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 168 ms 20984 KB Time limit exceeded (wall clock)
2 Execution timed out 157 ms 18808 KB Time limit exceeded (wall clock)
3 Execution timed out 164 ms 24440 KB Time limit exceeded (wall clock)
4 Execution timed out 22 ms 16640 KB Time limit exceeded (wall clock)
5 Execution timed out 23 ms 19840 KB Time limit exceeded (wall clock)
6 Execution timed out 32 ms 18168 KB Time limit exceeded (wall clock)
7 Execution timed out 45 ms 19064 KB Time limit exceeded (wall clock)
8 Execution timed out 55 ms 27960 KB Time limit exceeded (wall clock)
9 Execution timed out 105 ms 24952 KB Time limit exceeded (wall clock)
10 Execution timed out 80 ms 34296 KB Time limit exceeded (wall clock)
11 Execution timed out 120 ms 23672 KB Time limit exceeded (wall clock)
12 Execution timed out 279 ms 28924 KB Time limit exceeded (wall clock)
13 Execution timed out 217 ms 30072 KB Time limit exceeded (wall clock)
14 Execution timed out 1709 ms 64268 KB Time limit exceeded (wall clock)
15 Execution timed out 239 ms 39928 KB Time limit exceeded (wall clock)
16 Execution timed out 237 ms 53112 KB Time limit exceeded (wall clock)
17 Execution timed out 2128 ms 93816 KB Time limit exceeded (wall clock)