oj.uz

답안 #595380

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
595380 2022-07-13T16:57:18 Z Do_you_copy Regions (IOI09_regions) C++17
75 / 100
 5554 ms 131072 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 3e5 + 1;
const int maxR = 25000 + 1;
int n, r, q, sq;
vector <int> color[maxR];
vector <int> adj[maxN];
vector <vector<ll>> cnt, rcnt;
int pos[maxN], be[maxN], child[maxN];
int dpos[maxN], time_in;
int bit[maxN];

void update(int x, int val){
    for (; x <= n; x += x & -x){
        bit[x] += val;
    }
}

int get(int x){
    int sum = 0;
    for (; x; x -= x & -x){
        sum += bit[x];
    }
    return sum;
}

void pre_dfs(int u){
    dpos[u] = ++time_in;
    for (const int &i: adj[u]){
        pre_dfs(i);
        child[u] += child[i] + 1;
    }
}

int dfs(int u, int c, int up = 0){
    ll summ = 0;
    if (be[u] == c) ++up;
    else rcnt[rcnt.size() - 1][be[u]] += up;
    for (const int &i: adj[u]){
        summ += dfs(i, c, up);
    }
    if (be[u] == c) return summ + 1;
    cnt[cnt.size() - 1][be[u]] += summ;
    return summ;
}

void Init(){
    cin >> n >> r >> q;
    sq = sqrt(n) + 1;
    int t; cin >> t;
    be[1] = t;
    color[t].pb(1);
    for (int i = 2; i <= n; ++i){
        int p, t;
        cin >> p >> t;
        color[t].pb(i);
        be[i] = t;
        adj[p].pb(i);
    }
    pre_dfs(1);
    for (int i = 1; i <= r; ++i){
        if (color[i].size() >= sq){
            pos[i] = cnt.size();
            cnt.pb({});
            rcnt.pb({});
            cnt.back().resize(maxN, 0);
            rcnt.back().resize(maxN, 0);
            dfs(1, i);
        }
    }
    for (int i = 1; i <= q; ++i){
        int u, v;
        cin >> u >> v;
        if (color[v].size() >= sq){
            cout << cnt[pos[v]][u] << endl;
        }
        else if (color[u].size() >= sq){
            cout << rcnt[pos[u]][v] << endl;
        }
        else{
            for (const int &i: color[v]){
                update(dpos[i], 1);
            }
            ll ans = 0;
            for (const int &i: color[u]){
                ans += get(dpos[i] + child[i]) - get(dpos[i]);
            }
            cout << ans << endl;
            for (const int &i: color[v]){
                update(dpos[i], -1);
            }
        }
    }
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message

regions.cpp: In function 'void Init()':
regions.cpp:86:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         if (color[i].size() >= sq){
      |             ~~~~~~~~~~~~~~~~^~~~~
regions.cpp:98:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |         if (color[v].size() >= sq){
      |             ~~~~~~~~~~~~~~~~^~~~~
regions.cpp:101:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |         else if (color[u].size() >= sq){
      |                  ~~~~~~~~~~~~~~~~^~~~~
regions.cpp: In function 'int main()':
regions.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12624 KB Output is correct
2 Correct 6 ms 7876 KB Output is correct
3 Correct 5 ms 7888 KB Output is correct
4 Correct 10 ms 7888 KB Output is correct
5 Correct 15 ms 7888 KB Output is correct
6 Correct 21 ms 8116 KB Output is correct
7 Correct 16 ms 8016 KB Output is correct
8 Correct 57 ms 8016 KB Output is correct
9 Correct 33 ms 8400 KB Output is correct
10 Correct 103 ms 8400 KB Output is correct
11 Correct 92 ms 8736 KB Output is correct
12 Correct 188 ms 9248 KB Output is correct
13 Correct 169 ms 8904 KB Output is correct
14 Correct 339 ms 23580 KB Output is correct
15 Correct 383 ms 17328 KB Output is correct

Subtask #2
60.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1479 ms 120752 KB Output is correct
2 Correct 1724 ms 72404 KB Output is correct
3 Correct 3142 ms 61804 KB Output is correct
4 Correct 395 ms 9492 KB Output is correct
5 Correct 348 ms 11088 KB Output is correct
6 Runtime error 134 ms 131072 KB Execution killed with signal 9
7 Runtime error 197 ms 131072 KB Execution killed with signal 9
8 Runtime error 135 ms 131072 KB Execution killed with signal 9
9 Correct 3607 ms 16732 KB Output is correct
10 Runtime error 221 ms 131072 KB Execution killed with signal 9
11 Correct 5554 ms 16480 KB Output is correct
12 Correct 1531 ms 27612 KB Output is correct
13 Correct 2153 ms 28048 KB Output is correct
14 Correct 2432 ms 121524 KB Output is correct
15 Correct 3933 ms 32656 KB Output is correct
16 Correct 4313 ms 40088 KB Output is correct
17 Runtime error 227 ms 131072 KB Execution killed with signal 9