oj.uz

Submission #1051745

# Submission time Handle Problem Language Result Execution time Memory
1051745 2024-08-10T09:25:57 Z Ludissey Regions (IOI09_regions) C++17
25 / 100
 8000 ms 129284 KB 
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
 
using namespace std;

vector<vector<int>> child;
vector<int> parent;
vector<vector<pair<int,int>>> up;
unordered_map<int,int> conv;
vector<int> rg;
vector<vector<int>> pr;
int need;
int sq;
vector<int> tin;
vector<int> out;
int timer=0;


vector<int> setup_down(int x){
    vector<int> cv(sq);
    for (auto u : child[x]) {
        vector<int> v=setup_down(u);
        for (int i=0; i<sq; i++)
        {
            up[conv[rg[x]]][i].second+=v[i];
            cv[i]+=v[i];
        }
    }
    if(conv[rg[x]]<sq){
        up[conv[rg[x]]][conv[rg[x]]].second++;
        cv[conv[rg[x]]]++;
    }
    return cv;
}

void setup_up(int x, vector<int> rm){
    for (int i=0; i<sz(rm); i++)
    {
        up[conv[rg[x]]][i].first+=rm[i];
    }
    if(conv[rg[x]]<sq){
        up[conv[rg[x]]][conv[rg[x]]].first++;
        rm[conv[rg[x]]]++;
    }
    for (auto u : child[x]) setup_up(u,rm);
    return;
}

void setup_euler(int x){
    tin[x]=timer++;
    for (auto u : child[x]) setup_euler(u);
    out[x]=timer++;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N,R,Q; cin >> N >> R >> Q;
    sq=501;
    child.resize(N);
    parent.resize(N);
    up.resize(R,vector<pair<int,int>>(sq));
    rg.resize(N);
    tin.resize(N);
    out.resize(N);
    pr.resize(R);
    cin >> rg[0]; rg[0]--;
    vector<pair<int,int>> cnt(R);
    pr[rg[0]].push_back(0);
    cnt[rg[0]].first++;
    for (int i = 1; i < N; i++)
    {
        cin >> parent[i] >> rg[i]; parent[i]--; rg[i]--;
        child[parent[i]].push_back(i);
        pr[rg[i]].push_back(i);
        cnt[rg[i]].first++;
    }
    for (int i = 0; i < R; i++) cnt[i].second=i;
    
    sort(all(cnt),[&](auto &aa, auto &bb){return aa>bb; });
    for (int i = 0; i < sz(cnt); i++)
    {
        conv[cnt[i].second]=i;
    }
    vector<int> ep(sq);
    timer=0;
    setup_euler(0);
    timer++;
    //setup_up(0,ep);
    //setup_down(0);
    vector<int> t;
    t.resize(timer*2+1,0);
    for (int i = 0; i < Q; i++)
    {
        int sm=0;
        int e1,e2; cin >> e1>>e2; e1--; e2--;
        vector<pair<int,pair<int,int>>> tos;
        for (int j = 0; j < sz(pr[e1]); j++) {
            int in1=tin[pr[e1][j]], out1=out[pr[e1][j]];
            tos.push_back({in1,{out1,1}});
        }   
        for (int j = 0; j < sz(pr[e2]); j++)
        {
            int in1=tin[pr[e2][j]], out1=out[pr[e2][j]];
            tos.push_back({in1,{out1,2}});

        }
        sort(all(tos));
        int ones=0;
        unordered_set<int> todeval;
        for (int j = 0; j < sz(tos); j++)
        {
            if(tos[j].second.second==1) {
                ones++;
                int p=tos[j].second.first;
                todeval.insert(p + timer);
                for (t[p +=  timer] = 1; p > 1; p >>= 1) {
                    t[p>>1] = t[p] + t[p^1];
                    todeval.insert(p>>1);
                }
            }
            else{
                int csum=0;
                int l=0;
                int r=tos[j].second.first+1;
                for (l +=  timer, r += timer; l < r; l >>= 1, r >>= 1) {
                    if (l&1) csum += t[l++];
                    if (r&1) csum += t[--r];
                }
                sm+=ones-csum;
            }
        }
        for (auto u : todeval)
        {
            t[u]=0;
        }
        cout << sm << endl;
    }
    
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 9 ms 600 KB Output is correct
6 Correct 11 ms 1368 KB Output is correct
7 Correct 27 ms 1112 KB Output is correct
8 Correct 35 ms 1368 KB Output is correct
9 Correct 73 ms 2136 KB Output is correct
10 Correct 168 ms 3080 KB Output is correct
11 Correct 476 ms 2904 KB Output is correct
12 Correct 480 ms 4288 KB Output is correct
13 Correct 828 ms 3740 KB Output is correct
14 Correct 1731 ms 4176 KB Output is correct
15 Correct 2189 ms 6472 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8074 ms 11816 KB Time limit exceeded
2 Execution timed out 8023 ms 10956 KB Time limit exceeded
3 Execution timed out 8015 ms 14172 KB Time limit exceeded
4 Correct 1476 ms 19332 KB Output is correct
5 Correct 1354 ms 24872 KB Output is correct
6 Execution timed out 8004 ms 33556 KB Time limit exceeded
7 Execution timed out 8023 ms 47220 KB Time limit exceeded
8 Execution timed out 8023 ms 53328 KB Time limit exceeded
9 Execution timed out 8098 ms 75344 KB Time limit exceeded
10 Execution timed out 8031 ms 120264 KB Time limit exceeded
11 Execution timed out 8051 ms 117420 KB Time limit exceeded
12 Execution timed out 8012 ms 86312 KB Time limit exceeded
13 Execution timed out 8090 ms 87568 KB Time limit exceeded
14 Execution timed out 8100 ms 103900 KB Time limit exceeded
15 Execution timed out 8018 ms 127420 KB Time limit exceeded
16 Execution timed out 8079 ms 129284 KB Time limit exceeded
17 Execution timed out 8010 ms 108104 KB Time limit exceeded