oj.uz

Submission #519886

# Submission time Handle Problem Language Result Execution time Memory
519886 2022-01-27T14:11:19 Z LptN21 Regions (IOI09_regions) C++14
0 / 100
 106 ms 38816 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 = 106;


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 9 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 11 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 11 ms 19956 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 12 ms 20252 KB Time limit exceeded (wall clock)
11 Execution timed out 13 ms 20552 KB Time limit exceeded (wall clock)
12 Execution timed out 18 ms 21064 KB Time limit exceeded (wall clock)
13 Execution timed out 19 ms 20668 KB Time limit exceeded (wall clock)
14 Execution timed out 17 ms 21192 KB Time limit exceeded (wall clock)
15 Execution timed out 19 ms 23720 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 28 ms 24100 KB Time limit exceeded (wall clock)
2 Execution timed out 30 ms 22848 KB Time limit exceeded (wall clock)
3 Execution timed out 32 ms 25792 KB Time limit exceeded (wall clock)
4 Execution timed out 18 ms 21300 KB Time limit exceeded (wall clock)
5 Execution timed out 24 ms 22820 KB Time limit exceeded (wall clock)
6 Execution timed out 25 ms 22336 KB Time limit exceeded (wall clock)
7 Execution timed out 34 ms 23232 KB Time limit exceeded (wall clock)
8 Execution timed out 42 ms 27988 KB Time limit exceeded (wall clock)
9 Execution timed out 60 ms 28072 KB Time limit exceeded (wall clock)
10 Execution timed out 59 ms 32704 KB Time limit exceeded (wall clock)
11 Execution timed out 84 ms 27508 KB Time limit exceeded (wall clock)
12 Execution timed out 93 ms 29328 KB Time limit exceeded (wall clock)
13 Execution timed out 79 ms 29508 KB Time limit exceeded (wall clock)
14 Execution timed out 106 ms 29180 KB Time limit exceeded (wall clock)
15 Execution timed out 71 ms 33284 KB Time limit exceeded (wall clock)
16 Execution timed out 75 ms 38816 KB Time limit exceeded (wall clock)
17 Execution timed out 71 ms 37568 KB Time limit exceeded (wall clock)