oj.uz

답안 #311376

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
311376 2020-10-10T02:55:24 Z caoash Regions (IOI09_regions) C++14
0 / 100
 4134 ms 129768 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 << endl;
        } else {
            assert(pre.find(mp(qu, qv)) != pre.end());
            cout << pre[mp(qu, qv)] << endl;
        }
    }
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 14976 KB Output isn't correct
2 Incorrect 11 ms 14976 KB Output isn't correct
3 Incorrect 11 ms 14976 KB Output isn't correct
4 Incorrect 14 ms 15104 KB Output isn't correct
5 Incorrect 17 ms 15104 KB Output isn't correct
6 Incorrect 25 ms 15360 KB Output isn't correct
7 Incorrect 34 ms 15104 KB Output isn't correct
8 Incorrect 39 ms 15104 KB Output isn't correct
9 Incorrect 47 ms 15872 KB Output isn't correct
10 Incorrect 78 ms 15616 KB Output isn't correct
11 Incorrect 92 ms 15872 KB Output isn't correct
12 Incorrect 118 ms 16640 KB Output isn't correct
13 Incorrect 94 ms 16000 KB Output isn't correct
14 Incorrect 145 ms 16512 KB Output isn't correct
15 Incorrect 140 ms 21504 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 834 ms 21008 KB Output isn't correct
2 Incorrect 1012 ms 18836 KB Output isn't correct
3 Incorrect 1226 ms 24572 KB Output isn't correct
4 Incorrect 205 ms 16640 KB Output isn't correct
5 Incorrect 304 ms 19840 KB Output isn't correct
6 Incorrect 364 ms 18176 KB Output isn't correct
7 Incorrect 801 ms 19064 KB Output isn't correct
8 Incorrect 782 ms 27896 KB Output isn't correct
9 Incorrect 1192 ms 25080 KB Output isn't correct
10 Incorrect 1343 ms 34296 KB Output isn't correct
11 Incorrect 1731 ms 23672 KB Output isn't correct
12 Runtime error 320 ms 58744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 259 ms 60792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 1795 ms 129768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 336 ms 80760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Incorrect 1966 ms 52984 KB Output isn't correct
17 Incorrect 4134 ms 93804 KB Output isn't correct