oj.uz

Submission #1106866

# Submission time Handle Problem Language Result Execution time Memory
1106866 2024-10-31T08:15:53 Z Yang8on Regions (IOI09_regions) C++17
0 / 100
 1774 ms 131072 KB 
#include <bits/stdc++.h>
#define Y8o "REGIONS"
#define maxn (int) 2e5 + 5
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
#define all(x) x.begin(), x.end()
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define fi(i, a, b) for(int i = a; i <= b; i ++)
#define fid(i, a, b) for(int i = a; i >= b; i --)

//#define f first
//#define s second

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

const int can = 160;

int n, m, Q, cnt;
int a[maxn];
vector<int> o[maxn], pos[(int)25e3 + 5];
vector<pii> cur;
int in[maxn], out[maxn], vir[maxn], dem[maxn];
int ans_dw[165][(int)25e3 + 5], ans_up[165][(int)25e3 + 5];

void pre_dfs(int u = 1) {
    in[u] = ++cnt;
    for(int v : o[u]) {
        pre_dfs(v);
    }
    out[u] = cnt;
}

void dfs(int u, int cl, int d) {
    d += (a[u] == cl);
    dem[u] = 0;
    for(int v : o[u]) {
        ans_dw[vir[cl]][a[v]] += d;
        dfs(v, cl, d);
        dem[u] += dem[v];
    }
    ans_up[vir[cl]][a[u]] = dem[u];
    dem[u] += (a[u] == cl);
}

void solve() {
    cin >> n >> m >> Q;
    fi(i, 1, n) {
        if(i > 1) {
            int u; cin >> u;
            o[u].push_back(i);
        }
        cin >> a[i], pos[a[i]].push_back(i);
    }

    pre_dfs();

    cnt = 0;
    fi(i, 1, m) {
        if(pos[i].size() > can) {
            vir[i] = ++cnt;
            dfs(1, i, 0);
        }
        sort( all(pos[i]), [](int x, int y) { return in[x] < in[y]; });
    }

    fi(_, 1, Q) {
        int u, v; cin >> u >> v;
        if(pos[u].size() > can) cout << ans_dw[vir[u]][v] << '\n';
        else if(pos[v].size() > can) cout << ans_up[vir[v]][u] << '\n';
        else {
            cur.clear();
            fi(i, 0, pos[u].size() - 1) {
                int node = pos[u][i];
                cur.push_back({ in[node], +1 }), cur.push_back({ out[node] + 1, -1 });
            }
            sort(all(cur));

            int j = 0, op = 0; ll res = 0;
            fi(i, 0, pos[v].size() - 1) {
                int node = pos[v][i];
                while(j < cur.size() && cur[j].first <= in[node]) op += cur[j ++].second;
                res += op;
            }
            cout << res << '\n';
        }
    }
}


int main() {
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --) {
        solve();
    }

    ctime();
    return 0;
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:10:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define fi(i, a, b) for(int i = a; i <= b; i ++)
......
   91 |             fi(i, 0, pos[u].size() - 1) {
      |                ~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:91:13: note: in expansion of macro 'fi'
   91 |             fi(i, 0, pos[u].size() - 1) {
      |             ^~
regions.cpp:10:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define fi(i, a, b) for(int i = a; i <= b; i ++)
......
   98 |             fi(i, 0, pos[v].size() - 1) {
      |                ~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:98:13: note: in expansion of macro 'fi'
   98 |             fi(i, 0, pos[v].size() - 1) {
      |             ^~
regions.cpp:100:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |                 while(j < cur.size() && cur[j].first <= in[node]) op += cur[j ++].second;
      |                       ~~^~~~~~~~~~~~
regions.cpp: In function 'void iof()':
regions.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 17232 KB Execution killed with signal 11
2 Execution timed out 2 ms 8528 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 8528 KB Time limit exceeded (wall clock)
4 Execution timed out 2 ms 8528 KB Time limit exceeded (wall clock)
5 Execution timed out 2 ms 8528 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 8528 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 8528 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 8528 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 8784 KB Time limit exceeded (wall clock)
10 Execution timed out 4 ms 8784 KB Time limit exceeded (wall clock)
11 Execution timed out 4 ms 9040 KB Time limit exceeded (wall clock)
12 Execution timed out 7 ms 9296 KB Time limit exceeded (wall clock)
13 Execution timed out 6 ms 9040 KB Time limit exceeded (wall clock)
14 Execution timed out 38 ms 21840 KB Time limit exceeded (wall clock)
15 Execution timed out 94 ms 46744 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 320 ms 45384 KB Time limit exceeded (wall clock)
2 Execution timed out 288 ms 43640 KB Time limit exceeded (wall clock)
3 Runtime error 324 ms 96892 KB Execution killed with signal 11
4 Execution timed out 29 ms 22096 KB Time limit exceeded (wall clock)
5 Execution timed out 14 ms 10576 KB Time limit exceeded (wall clock)
6 Execution timed out 92 ms 27208 KB Time limit exceeded (wall clock)
7 Execution timed out 159 ms 31816 KB Time limit exceeded (wall clock)
8 Execution timed out 174 ms 43592 KB Time limit exceeded (wall clock)
9 Execution timed out 477 ms 40612 KB Time limit exceeded (wall clock)
10 Runtime error 770 ms 114948 KB Execution killed with signal 11
11 Runtime error 1154 ms 95392 KB Execution killed with signal 11
12 Runtime error 1774 ms 99400 KB Execution killed with signal 11
13 Runtime error 1356 ms 101068 KB Execution killed with signal 11
14 Runtime error 1564 ms 99260 KB Execution killed with signal 11
15 Runtime error 1014 ms 113480 KB Execution killed with signal 11
16 Runtime error 1260 ms 131072 KB Execution killed with signal 9
17 Runtime error 1182 ms 131072 KB Execution killed with signal 9