oj.uz

답안 #595392

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
595392 2022-07-13T17:07:19 Z Do_you_copy Regions (IOI09_regions) C++17
75 / 100
 7167 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 <ll, ll>;
using pil = pair <ll, ll>;
using pli = pair <ll, ll>;
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 ll maxN = 3e5 + 1;
const ll maxR = 3e4;
ll n, r, q, sq;
vector <ll> color[maxR];
vector <ll> adj[maxN];
vector <vector<ll>> cnt, rcnt;
ll pos[maxN], be[maxN], child[maxN];
ll dpos[maxN], time_in;
ll bit[maxN];

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

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

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

ll dfs(ll u, ll c, ll up = 0){
    ll summ = 0;
    if (be[u] == c) ++up;
    else rcnt[rcnt.size() - 1][be[u]] += up;
    for (const ll &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;
    ll t; cin >> t;
    be[1] = t;
    color[t].pb(1);
    for (ll i = 2; i <= n; ++i){
        ll p, t;
        cin >> p >> t;
        color[t].pb(i);
        be[i] = t;
        adj[p].pb(i);
    }
    pre_dfs(1);
    for (ll 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 (ll i = 1; i <= q; ++i){
        ll 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 ll &i: color[v]){
                update(dpos[i], 1);
            }
            ll ans = 0;
            for (const ll &i: color[u]){
                ans += get(dpos[i] + child[i]) - get(dpos[i]);
            }
            cout << ans << endl;
            for (const ll &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<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   86 |         if (color[i].size() >= sq){
      |             ~~~~~~~~~~~~~~~~^~~~~
regions.cpp:98:29: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   98 |         if (color[v].size() >= sq){
      |             ~~~~~~~~~~~~~~~~^~~~~
regions.cpp:101:34: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long 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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12696 KB Output is correct
2 Correct 6 ms 8012 KB Output is correct
3 Correct 6 ms 8048 KB Output is correct
4 Correct 9 ms 8016 KB Output is correct
5 Correct 10 ms 8120 KB Output is correct
6 Correct 19 ms 8144 KB Output is correct
7 Correct 17 ms 8144 KB Output is correct
8 Correct 29 ms 8272 KB Output is correct
9 Correct 52 ms 8656 KB Output is correct
10 Correct 103 ms 8724 KB Output is correct
11 Correct 136 ms 9168 KB Output is correct
12 Correct 175 ms 9808 KB Output is correct
13 Correct 247 ms 9552 KB Output is correct
14 Correct 323 ms 24384 KB Output is correct
15 Correct 448 ms 18276 KB Output is correct

Subtask #2
60.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1335 ms 122408 KB Output is correct
2 Correct 1459 ms 74340 KB Output is correct
3 Correct 2992 ms 63744 KB Output is correct
4 Correct 378 ms 10192 KB Output is correct
5 Correct 447 ms 12028 KB Output is correct
6 Runtime error 123 ms 131072 KB Execution killed with signal 9
7 Runtime error 202 ms 131072 KB Execution killed with signal 9
8 Runtime error 146 ms 131072 KB Execution killed with signal 9
9 Correct 3905 ms 20044 KB Output is correct
10 Runtime error 206 ms 131072 KB Execution killed with signal 9
11 Correct 7167 ms 21020 KB Output is correct
12 Correct 2321 ms 31576 KB Output is correct
13 Correct 2653 ms 32080 KB Output is correct
14 Correct 3258 ms 125920 KB Output is correct
15 Correct 4339 ms 36664 KB Output is correct
16 Correct 4313 ms 43976 KB Output is correct
17 Runtime error 221 ms 131072 KB Execution killed with signal 9