oj.uz

Submission #939903

# Submission time Handle Problem Language Result Execution time Memory
939903 2024-03-06T23:32:37 Z idiotcomputer Regions (IOI09_regions) C++11
0 / 100
 122 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int 
#define sz size

const int mxN = 2e5;
const int mxR = 25*1e3;
int n,r;

vector<int> adj[mxN];
int reg[mxN];
vector<int> all[mxR];
int first[mxN];
int ssize[mxN];
vector<int> ord;

vector<ll> cnts[mxR];
vector<ll> rcnts[mxR];
int tarr[mxN+1];

void dfs(int node, int p){
    first[node] = ord.sz();
    all[reg[node]].pb(node);
    ord.pb(node);
    ssize[node] = 1;
    for (int next : adj[node]){
        if (next != p){
            dfs(next,node);
            ssize[node] += ssize[next];
        }
    }
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int q;
    cin >> n >> r >> q;
    int a,b;
    cin >> a;
    reg[0] = a-1;
    for (int i = 1; i < n; i++){
        cin >> b >> a;
        a -= 1;
        b -= 1;
        reg[i] = a;
        adj[i].pb(b);
        adj[b].pb(i);
    }
    
    dfs(0,-1);
    int gsize = sqrt(n);
    for (int i = 0; i < r; i++){
        if (all[i].sz() <= gsize){
            continue;
        }
        cnts[i].resize(n);
        memset(tarr,0,sizeof(tarr));
        for (int j =0; j < all[i].sz(); j++){
            tarr[first[all[i][j]]] += 1;
            tarr[first[all[i][j]] + ssize[all[i][j]]] -= 1;
        }
        for (int j = 0; j < n; j++){
            if (j > 0) tarr[j] += tarr[j-1];
            cnts[i][reg[ord[j]]] += tarr[j];
        }
        rcnts[i].resize(n);
        memset(tarr,0,sizeof(tarr));
        for (int j =0; j < all[i].sz(); j++){
            tarr[first[all[i][j]]] += 1;
        }
        for (int j = 1; j < n; j++){
            tarr[j] += tarr[j-1];
        }
        for (int j = 0; j < n; j++){
            rcnts[i][reg[ord[j]]] += tarr[j+ssize[ord[j]]-1] - tarr[j];
        }
    }
    /*cout << gsize<< " gsize\n";
    for (int i =0; i < r; i++){
        cout << all[i].sz() << ":\n";
        for (int j = 0; j < all[i].sz(); j++) cout << all[i][j] << " ";
        cout << '\n';
        if (all[i].sz() <= gsize){
            continue;
        }
        for (int j =0; j < n; j++){
            cout << cnts[i][j] << " ";
        }
        cout << '\n';
        for (int j = 0; j < n; j++) cout << rcnts[i][j] << " ";
        cout << '\n';
    }
    */
    int c,idx;
    stack<int> p;
    ll res;
    for (int i =0; i < q; i++){
        cin >> a >> b;
        a -= 1;
        b -= 1;
        if (all[a].sz() > gsize){
            cout << cnts[a][b] << '\n';
            continue;
        }
        if (all[b].sz() > gsize){
            cout << rcnts[b][a] << "\n";
            continue;
        }
        c = 0;
        idx = 0;
        res = 0;
        for (int j = 0; j < all[b].sz(); j++){
            while (p.sz() > 0 && p.top() <= j){
                p.pop();
                c -= 1;
            }
            while (idx < all[a].sz() && all[a][idx] <= j){
                c += 1;
                idx++;
                p.push(first[all[a][idx]] + ssize[all[a][idx]]);
            }
            res += c;
        }
        cout << res << '\n';
        while (p.sz() > 0){
            p.pop();
        }
    }
    
    
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:59:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |         if (all[i].sz() <= gsize){
      |             ~~~~~~~~~~~~^~~~~~~~
regions.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int j =0; j < all[i].sz(); j++){
      |                        ~~^~~~~~~~~~~~~
regions.cpp:74:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for (int j =0; j < all[i].sz(); j++){
      |                        ~~^~~~~~~~~~~~~
regions.cpp:107:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |         if (all[a].sz() > gsize){
      |             ~~~~~~~~~~~~^~~~~~~
regions.cpp:111:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |         if (all[b].sz() > gsize){
      |             ~~~~~~~~~~~~^~~~~~~
regions.cpp:118:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for (int j = 0; j < all[b].sz(); j++){
      |                         ~~^~~~~~~~~~~~~
regions.cpp:123:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             while (idx < all[a].sz() && all[a][idx] <= j){
      |                    ~~~~^~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4 ms 9816 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 9816 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 9816 KB Time limit exceeded (wall clock)
4 Execution timed out 2 ms 9816 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 9816 KB Time limit exceeded (wall clock)
6 Execution timed out 2 ms 9816 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 9812 KB Time limit exceeded (wall clock)
8 Execution timed out 2 ms 9816 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 10328 KB Time limit exceeded (wall clock)
10 Execution timed out 4 ms 10328 KB Time limit exceeded (wall clock)
11 Execution timed out 7 ms 10328 KB Time limit exceeded (wall clock)
12 Execution timed out 8 ms 10852 KB Time limit exceeded (wall clock)
13 Execution timed out 8 ms 10832 KB Time limit exceeded (wall clock)
14 Execution timed out 10 ms 12632 KB Time limit exceeded (wall clock)
15 Execution timed out 11 ms 14804 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 38 ms 41024 KB Time limit exceeded (wall clock)
2 Execution timed out 32 ms 29832 KB Time limit exceeded (wall clock)
3 Execution timed out 32 ms 29968 KB Time limit exceeded (wall clock)
4 Execution timed out 10 ms 11084 KB Time limit exceeded (wall clock)
5 Execution timed out 10 ms 12940 KB Time limit exceeded (wall clock)
6 Execution timed out 57 ms 61460 KB Time limit exceeded (wall clock)
7 Execution timed out 61 ms 68276 KB Time limit exceeded (wall clock)
8 Runtime error 108 ms 131072 KB Execution killed with signal 9
9 Execution timed out 38 ms 17860 KB Time limit exceeded (wall clock)
10 Runtime error 122 ms 131072 KB Execution killed with signal 9
11 Execution timed out 55 ms 18988 KB Time limit exceeded (wall clock)
12 Execution timed out 62 ms 24084 KB Time limit exceeded (wall clock)
13 Execution timed out 68 ms 25080 KB Time limit exceeded (wall clock)
14 Execution timed out 108 ms 87812 KB Time limit exceeded (wall clock)
15 Execution timed out 52 ms 29236 KB Time limit exceeded (wall clock)
16 Execution timed out 64 ms 36532 KB Time limit exceeded (wall clock)
17 Execution timed out 115 ms 100900 KB Time limit exceeded (wall clock)