oj.uz

답안 #311370

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
311370 2020-10-10T02:41:08 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

# 결과 실행 시간 메모리 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 13 ms 15104 KB Output is correct
5 Correct 21 ms 15232 KB Output is correct
6 Correct 64 ms 18424 KB Output is correct
7 Correct 83 ms 16632 KB Output is correct
8 Correct 120 ms 17784 KB Output is correct
9 Correct 443 ms 21624 KB Output is correct
10 Correct 1699 ms 26744 KB Output is correct
11 Correct 1126 ms 20712 KB Output is correct
12 Correct 3873 ms 29436 KB Output is correct
13 Correct 2696 ms 23288 KB Output is correct
14 Correct 1545 ms 19328 KB Output is correct
15 Correct 2436 ms 25400 KB Output is correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4660 ms 23348 KB Output isn't correct
2 Incorrect 5344 ms 22136 KB Output isn't correct
3 Execution timed out 8019 ms 28280 KB Time limit exceeded
4 Runtime error 3690 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 4790 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 4003 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 2392 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 4732 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 2995 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 4447 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 3726 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 5001 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Execution timed out 8012 ms 120384 KB Time limit exceeded
14 Execution timed out 8048 ms 79352 KB Time limit exceeded
15 Execution timed out 8098 ms 38260 KB Time limit exceeded
16 Execution timed out 8068 ms 54772 KB Time limit exceeded
17 Execution timed out 8013 ms 62136 KB Time limit exceeded