oj.uz

답안 #595338

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
595338 2022-07-13T16:08:43 Z Do_you_copy Regions (IOI09_regions) C++17
0 / 100
 242 ms 131072 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 1;
const int maxR = 25000 + 1;
int n, r, q, sq;
vector <int> color[maxR];
vector <int> adj[maxN];
vector <vector<ll>> cnt, rcnt;
int pos[maxN], be[maxN], child[maxN];
int dpos[maxN], time_in;
int bit[maxN];

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

int get(int x){
    int sum = 0;
    for (; x; x -= x & -x){
        sum += bit[x];
    }
    return sum;
}

void pre_dfs(int u){
    dpos[u] = ++time_in;
    for (const int &i: adj[u]){
        pre_dfs(i);
        child[u] += child[i] + 1;
    }
}

int dfs(int u, int c, int up = 0){
    int sum = 0;
    if (be[u] == c) ++up;
    else rcnt[rcnt.size() - 1][be[u]] += up;
    for (const int &i: adj[u]){
        sum += dfs(i, c, up);
    }
    if (be[u] == c) return sum + 1;
    cnt[cnt.size() - 1][be[u]] += sum;
    return sum;
}

void Init(){
    cin >> n >> r >> q;
    sq = sqrt(n) + 1;
    int t; cin >> t;
    be[1] = t;
    color[t].pb(1);
    for (int i = 2; i <= n; ++i){
        int p, t;
        cin >> p >> t;
        color[t].pb(i);
        be[i] = t;
        adj[p].pb(i);
    }
    pre_dfs(1);
    for (int i = 1; i <= r; ++i){
        if (color[i].size() >= sq){
            pos[i] = cnt.size();
            cnt.pb({});
            rcnt.pb({});
            cnt.back().resize(maxN, 0);
            rcnt.back().resize(maxN, 0);
            dfs(1, i);
        }
    }
    for (int i = 1; i <= q; ++i){
        int u, v;
        cin >> u >> v;
        if (color[v].size() >= sq){
            cout << cnt[pos[v]][u] << "\n";
        }
        else if (color[u].size() >= sq){
            cout << rcnt[pos[u]][v] << "\n";
        }
        else{
            for (const int &i: color[v]){
                update(dpos[i], 1);
            }
            ll ans = 0;
            for (const int &i: color[u]){
                ans += get(dpos[i] + child[i]) - get(dpos[i]);
            }
            cout << ans << "\n";
            for (const int &i: color[v]){
                update(dpos[i], -1);
            }
        }
    }
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message

regions.cpp: In function 'void Init()':
regions.cpp:86:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         if (color[i].size() >= sq){
      |             ~~~~~~~~~~~~~~~~^~~~~
regions.cpp:98:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |         if (color[v].size() >= sq){
      |             ~~~~~~~~~~~~~~~~^~~~~
regions.cpp:101:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |         else if (color[u].size() >= sq){
      |                  ~~~~~~~~~~~~~~~~^~~~~
regions.cpp: In function 'int main()':
regions.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3 ms 4816 KB Time limit exceeded (wall clock)
2 Execution timed out 2 ms 3152 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 3152 KB Time limit exceeded (wall clock)
4 Execution timed out 2 ms 3152 KB Time limit exceeded (wall clock)
5 Execution timed out 2 ms 3280 KB Time limit exceeded (wall clock)
6 Execution timed out 2 ms 3280 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 3280 KB Time limit exceeded (wall clock)
8 Execution timed out 2 ms 3280 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 3664 KB Time limit exceeded (wall clock)
10 Execution timed out 5 ms 3752 KB Time limit exceeded (wall clock)
11 Execution timed out 6 ms 4048 KB Time limit exceeded (wall clock)
12 Execution timed out 6 ms 4464 KB Time limit exceeded (wall clock)
13 Execution timed out 8 ms 4176 KB Time limit exceeded (wall clock)
14 Execution timed out 13 ms 9424 KB Time limit exceeded (wall clock)
15 Execution timed out 12 ms 9424 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 80 ms 43732 KB Time limit exceeded (wall clock)
2 Execution timed out 59 ms 26956 KB Time limit exceeded (wall clock)
3 Execution timed out 46 ms 25468 KB Time limit exceeded (wall clock)
4 Execution timed out 13 ms 4688 KB Time limit exceeded (wall clock)
5 Execution timed out 10 ms 6352 KB Time limit exceeded (wall clock)
6 Execution timed out 144 ms 100176 KB Time limit exceeded (wall clock)
7 Execution timed out 184 ms 85216 KB Time limit exceeded (wall clock)
8 Runtime error 242 ms 131072 KB Execution killed with signal 9
9 Runtime error 31 ms 14760 KB Execution killed with signal 6
10 Runtime error 29 ms 15492 KB Execution killed with signal 6
11 Runtime error 31 ms 12960 KB Execution killed with signal 6
12 Runtime error 32 ms 15108 KB Execution killed with signal 6
13 Runtime error 31 ms 14544 KB Execution killed with signal 6
14 Runtime error 32 ms 14280 KB Execution killed with signal 6
15 Runtime error 32 ms 15828 KB Execution killed with signal 6
16 Runtime error 36 ms 15612 KB Execution killed with signal 6
17 Runtime error 30 ms 15472 KB Execution killed with signal 6