oj.uz

Submission #1106847

# Submission time Handle Problem Language Result Execution time Memory
1106847 2024-10-31T07:55:02 Z Yang8on Regions (IOI09_regions) C++17
0 / 100
 8000 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[maxn];
vector<pii> cur;
int in[maxn], out[maxn], vir[maxn];
int ans[165][(int)25e4 + 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);
    for(int v : o[u]) {
        ans[cl][a[v]] += d;
        dfs(v, cl, d);
    }
}

void solve() {
    cin >> n >> m >> Q;
    fi(i, 1, n) {
        if(i == 1) cin >> a[i], pos[a[i]].push_back(i);
        else {
            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;
            for(int j : pos[i]) {
                dfs(j, 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[vir[u]][v] << '\n';
        else if(pos[v].size() > can) cout << ans[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 ++)
......
   90 |             fi(i, 0, pos[u].size() - 1) {
      |                ~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:90:13: note: in expansion of macro 'fi'
   90 |             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 ++)
......
   97 |             fi(i, 0, pos[v].size() - 1) {
      |                ~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:97:13: note: in expansion of macro 'fi'
   97 |             fi(i, 0, pos[v].size() - 1) {
      |             ^~
regions.cpp:99: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]
   99 |                 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 35 ms 26704 KB Execution killed with signal 11
2 Execution timed out 3 ms 13392 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 13392 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 13392 KB Time limit exceeded (wall clock)
5 Execution timed out 4 ms 13392 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 13392 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 13392 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 13404 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 13648 KB Time limit exceeded (wall clock)
10 Execution timed out 5 ms 13648 KB Time limit exceeded (wall clock)
11 Execution timed out 6 ms 13904 KB Time limit exceeded (wall clock)
12 Execution timed out 7 ms 14160 KB Time limit exceeded (wall clock)
13 Execution timed out 8 ms 13904 KB Time limit exceeded (wall clock)
14 Runtime error 384 ms 131072 KB Execution killed with signal 9
15 Runtime error 3016 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 6164 ms 131072 KB Execution killed with signal 9
2 Runtime error 979 ms 131072 KB Execution killed with signal 9
3 Execution timed out 8044 ms 130732 KB Time limit exceeded
4 Runtime error 51 ms 37664 KB Execution killed with signal 11
5 Execution timed out 11 ms 15440 KB Time limit exceeded (wall clock)
6 Runtime error 37 ms 30796 KB Execution killed with signal 11
7 Runtime error 71 ms 36936 KB Execution killed with signal 11
8 Runtime error 313 ms 54600 KB Execution killed with signal 11
9 Runtime error 73 ms 40116 KB Execution killed with signal 11
10 Runtime error 79 ms 46664 KB Execution killed with signal 11
11 Runtime error 71 ms 38984 KB Execution killed with signal 11
12 Runtime error 195 ms 67996 KB Execution killed with signal 11
13 Runtime error 429 ms 69448 KB Execution killed with signal 11
14 Runtime error 592 ms 59468 KB Execution killed with signal 11
15 Runtime error 578 ms 71752 KB Execution killed with signal 11
16 Runtime error 893 ms 86676 KB Execution killed with signal 11
17 Runtime error 2681 ms 86784 KB Execution killed with signal 11