oj.uz

Submission #1106851

# Submission time Handle Problem Language Result Execution time Memory
1106851 2024-10-31T07:58:06 Z Yang8on Regions (IOI09_regions) C++17
0 / 100
 8000 ms 79020 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];
int ans[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);
    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 13 ms 15184 KB Execution killed with signal 11
2 Execution timed out 2 ms 7504 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 7504 KB Time limit exceeded (wall clock)
4 Execution timed out 2 ms 7504 KB Time limit exceeded (wall clock)
5 Execution timed out 2 ms 7504 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 7504 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 7504 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 7504 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 7760 KB Time limit exceeded (wall clock)
10 Execution timed out 4 ms 8016 KB Time limit exceeded (wall clock)
11 Execution timed out 6 ms 8272 KB Time limit exceeded (wall clock)
12 Execution timed out 9 ms 8528 KB Time limit exceeded (wall clock)
13 Execution timed out 7 ms 8272 KB Time limit exceeded (wall clock)
14 Runtime error 69 ms 50760 KB Execution killed with signal 11
15 Runtime error 3539 ms 58068 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 7559 ms 56572 KB Execution killed with signal 11
2 Runtime error 1343 ms 53412 KB Execution killed with signal 11
3 Execution timed out 8074 ms 30404 KB Time limit exceeded
4 Runtime error 25 ms 25936 KB Execution killed with signal 11
5 Execution timed out 13 ms 9816 KB Time limit exceeded (wall clock)
6 Runtime error 36 ms 23368 KB Execution killed with signal 11
7 Runtime error 92 ms 25240 KB Execution killed with signal 11
8 Runtime error 310 ms 46948 KB Execution killed with signal 11
9 Runtime error 58 ms 32828 KB Execution killed with signal 11
10 Runtime error 89 ms 54776 KB Execution killed with signal 11
11 Runtime error 68 ms 31560 KB Execution killed with signal 11
12 Runtime error 216 ms 52116 KB Execution killed with signal 11
13 Runtime error 425 ms 53628 KB Execution killed with signal 11
14 Runtime error 583 ms 43592 KB Execution killed with signal 11
15 Runtime error 809 ms 64328 KB Execution killed with signal 11
16 Runtime error 1264 ms 79020 KB Execution killed with signal 11
17 Runtime error 2895 ms 70968 KB Execution killed with signal 11