oj.uz

Submission #519904

# Submission time Handle Problem Language Result Execution time Memory
519904 2022-01-27T14:29:00 Z LptN21 Regions (IOI09_regions) C++17
0 / 100
 99 ms 38764 KB 
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL);
#define PI acos(-1.0)
#define eps 1e-9
#define FF first
#define SS second
// VECTOR (6)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define uniq(v) sort(all( (v) )), (v).resize( unique(all( (v) )) - (v).begin() );
// BIT (6)
#define CNTBIT(x) __builtin_popcountll(x)
#define ODDBIT(x) __builtin_parityll(x)
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SUBSET(big, small) (((big)&(small))==(small))
#define MINBIT(x) (x)&(-x)
//typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, int> ii;

/* */
template<class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template<class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}
/* */

/* CODE BELOW */
const int N = 2e5 + 7, M = 1e9 + 7;
const int oo = 1e9 + 7;
const int MOD = 1e9 + 7;

int n, r, q;

const int BL = 206;


class FenwickTree{
private: int n;
    vector<int> bit;
public:
    FenwickTree(int _n = 0):n(_n) {
        bit.assign(_n + 1, 0);
    }

    void update(int p, int v) {
        for(;p<=n;p+=p&-p) {
            bit[p]+= v;
        }
    }

    int query(int l, int r) {
        int ans = 0;
        for(--l;l>0;l-=l&-l) ans-= bit[l];
        for(;r>0;r-=r&-r) ans+= bit[r];
        return ans;
    }
};

FenwickTree bit(N);

int in[N], out[N], cnt = 0;
vector<int> adj[N];
vector<int> region[N];

int cover[N];
int ans[N], type[N];
vector<ii> R1Group[N];
vector<ii> R2Group[N];
vector<ii> naiveQuery;

void dfs(int u) {
    region[type[u]].pb(u);
    in[u] = ++cnt;
    for(int v:adj[u]) dfs(v);
    out[u] = cnt;
}

int solve1(int u, int v) { // r1, r2 small
    int ans = 0;
    for(int x:region[v]) {
        bit.update(in[x], 1);
    }
    for(int x:region[u]) {
        ans+= bit.query(in[x], out[x]);
    }
    for(int x:region[v]) {
        bit.update(in[x], -1);
    }
    return ans;
}

void solve2() { // r1 big, r2 big/small
    for(int t=1;t<=r;t++) {
        if(sz(region[t])>M) {
            sort(all(R1Group[t]));
            for(int v:region[t]) {
                cover[in[v]]++;
                cover[out[v]+1]--;
            }
            for(int i=1;i<=n;i++) {
                cover[i]+= cover[i-1];
            }

            // process query
            int u, idx;
            for(int i=0;i<sz(R1Group[t]);i++) {
                tie(u, idx) = R1Group[t][i];
                if(i && R1Group[t][i-1].FF == u) {
                    ans[idx] = ans[R1Group[t][i-1].SS];
                    continue;
                }
                for(int v:region[u]) {
                    ans[idx]+= cover[in[v]];
                }
            }

            for(int i=1;i<=n;i++) cover[i] = 0;
        }
    }
}

void solve3() { // r1 big/small, r2 big
    for(int t=1;t<=r;t++) {
        if(sz(region[t])>M) {
            sort(all(R2Group[t]));
            for(int v:region[t]) {
                cover[in[v]]++;
            }
            for(int i=1;i<=n;i++) {
                cover[i]+= cover[i-1];
            }

            // process query
            int u, idx;
            for(int i=0;i<sz(R2Group[t]);i++) {
                tie(u, idx) = R2Group[t][i];
                if(i && R2Group[t][i-1].FF == u) {
                    ans[idx] = ans[R2Group[t][i-1].SS];
                    continue;
                }
                for(int v:region[u]) {
                    ans[idx]+= cover[out[v]] - cover[in[v]-1];
                }
            }

            for(int i=1;i<=n;i++) cover[i] = 0;
        }
    }
}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    //fastIO;
    scanf("%d%d%d", &n, &r, &q);
    int u, v; scanf("%d", &type[1]);
    for(int i=2;i<=n;i++) {
        scanf("%d%d", &u, &type[i]);
        adj[u].pb(i);
    }
    dfs(1);

    for(int i=1;i<=q;i++) {
        scanf("%d%d", &u, &v);
        if(sz(region[u])<=M&&
           sz(region[v])<=M) {
            ans[i] = solve1(u, v);
        }
        if(sz(region[u])>M) {
            R1Group[u].pb(ii(v, i));
        } else if(sz(region[v])>M) {
            R2Group[v].pb(ii(u, i));
        }
    }
    solve2(), solve3();

    for(int i=1;i<=q;i++) {
        printf("%d\n", ans[i]);
    }

    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |     scanf("%d%d%d", &n, &r, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:170:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |     int u, v; scanf("%d", &type[1]);
      |               ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:172:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         scanf("%d%d", &u, &type[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:178:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10 ms 19784 KB Time limit exceeded (wall clock)
2 Execution timed out 10 ms 19784 KB Time limit exceeded (wall clock)
3 Execution timed out 9 ms 19784 KB Time limit exceeded (wall clock)
4 Execution timed out 9 ms 19784 KB Time limit exceeded (wall clock)
5 Execution timed out 10 ms 19912 KB Time limit exceeded (wall clock)
6 Execution timed out 9 ms 19912 KB Time limit exceeded (wall clock)
7 Execution timed out 9 ms 19912 KB Time limit exceeded (wall clock)
8 Execution timed out 10 ms 19912 KB Time limit exceeded (wall clock)
9 Execution timed out 10 ms 20296 KB Time limit exceeded (wall clock)
10 Execution timed out 13 ms 20296 KB Time limit exceeded (wall clock)
11 Execution timed out 12 ms 20552 KB Time limit exceeded (wall clock)
12 Execution timed out 14 ms 21064 KB Time limit exceeded (wall clock)
13 Execution timed out 15 ms 20680 KB Time limit exceeded (wall clock)
14 Execution timed out 17 ms 21184 KB Time limit exceeded (wall clock)
15 Execution timed out 20 ms 23752 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 30 ms 24104 KB Time limit exceeded (wall clock)
2 Execution timed out 34 ms 22920 KB Time limit exceeded (wall clock)
3 Execution timed out 34 ms 25792 KB Time limit exceeded (wall clock)
4 Execution timed out 17 ms 21320 KB Time limit exceeded (wall clock)
5 Execution timed out 22 ms 22804 KB Time limit exceeded (wall clock)
6 Execution timed out 24 ms 22352 KB Time limit exceeded (wall clock)
7 Execution timed out 33 ms 23236 KB Time limit exceeded (wall clock)
8 Execution timed out 39 ms 28096 KB Time limit exceeded (wall clock)
9 Execution timed out 62 ms 27980 KB Time limit exceeded (wall clock)
10 Execution timed out 73 ms 32708 KB Time limit exceeded (wall clock)
11 Execution timed out 78 ms 27592 KB Time limit exceeded (wall clock)
12 Execution timed out 87 ms 29324 KB Time limit exceeded (wall clock)
13 Execution timed out 97 ms 29560 KB Time limit exceeded (wall clock)
14 Execution timed out 99 ms 29100 KB Time limit exceeded (wall clock)
15 Execution timed out 78 ms 33372 KB Time limit exceeded (wall clock)
16 Execution timed out 72 ms 38764 KB Time limit exceeded (wall clock)
17 Execution timed out 70 ms 37648 KB Time limit exceeded (wall clock)