oj.uz

Submission #595370

# Submission time Handle Problem Language Result Execution time Memory
595370 2022-07-13T16:52:16 Z Do_you_copy Regions (IOI09_regions) C++17
0 / 100
 540 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){
    int 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] << "\n";
        }
        else if (color[u].size() >= sq){
            cout << rcnt[pos[u]][v] << "\n";
        }
        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 << "\n";
            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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6 ms 12624 KB Time limit exceeded (wall clock)
2 Execution timed out 4 ms 7888 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 7888 KB Time limit exceeded (wall clock)
4 Execution timed out 4 ms 7888 KB Time limit exceeded (wall clock)
5 Execution timed out 4 ms 7888 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 8016 KB Time limit exceeded (wall clock)
7 Execution timed out 5 ms 8016 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 8016 KB Time limit exceeded (wall clock)
9 Execution timed out 5 ms 8400 KB Time limit exceeded (wall clock)
10 Execution timed out 10 ms 8400 KB Time limit exceeded (wall clock)
11 Execution timed out 9 ms 8656 KB Time limit exceeded (wall clock)
12 Execution timed out 8 ms 9168 KB Time limit exceeded (wall clock)
13 Execution timed out 11 ms 8784 KB Time limit exceeded (wall clock)
14 Execution timed out 23 ms 23504 KB Time limit exceeded (wall clock)
15 Execution timed out 16 ms 17324 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 125 ms 120428 KB Time limit exceeded (wall clock)
2 Execution timed out 91 ms 72280 KB Time limit exceeded (wall clock)
3 Execution timed out 64 ms 61336 KB Time limit exceeded (wall clock)
4 Execution timed out 14 ms 9424 KB Time limit exceeded (wall clock)
5 Execution timed out 15 ms 10960 KB Time limit exceeded (wall clock)
6 Runtime error 121 ms 131072 KB Execution killed with signal 9
7 Runtime error 168 ms 131072 KB Execution killed with signal 9
8 Runtime error 143 ms 131072 KB Execution killed with signal 9
9 Execution timed out 53 ms 16328 KB Time limit exceeded (wall clock)
10 Runtime error 194 ms 131072 KB Execution killed with signal 9
11 Execution timed out 61 ms 16212 KB Time limit exceeded (wall clock)
12 Execution timed out 125 ms 26812 KB Time limit exceeded (wall clock)
13 Execution timed out 119 ms 27224 KB Time limit exceeded (wall clock)
14 Execution timed out 540 ms 121320 KB Time limit exceeded (wall clock)
15 Execution timed out 89 ms 32516 KB Time limit exceeded (wall clock)
16 Execution timed out 101 ms 39176 KB Time limit exceeded (wall clock)
17 Runtime error 236 ms 131072 KB Execution killed with signal 9