oj.uz

Submission #1051051

# Submission time Handle Problem Language Result Execution time Memory
1051051 2024-08-09T18:55:53 Z Ludissey Regions (IOI09_regions) C++17
30 / 100
 8000 ms 131072 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<int>> up;
vector<vector<int>> down;
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++)
        {
            down[conv[rg[x]]][i]+=v[i];
            cv[i]+=v[i];
        }
    }
    if(conv[rg[x]]<sq){
        down[conv[rg[x]]][conv[rg[x]]]++;
        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]+=rm[i];
    }
    if(conv[rg[x]]<sq){
        up[conv[rg[x]]][conv[rg[x]]]++;
        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=500;
    child.resize(N);
    parent.resize(N);
    up.resize(R,vector<int>(sq));
    down.resize(R,vector<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);
    setup_up(0,ep);
    setup_down(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;
        vector<int> forCONV;
        unordered_map<int,int> conv2;
        for (int j = 0; j < sz(pr[e1]); j++)
        {
            int in1=tin[pr[e1][j]], out1=out[pr[e1][j]];
            forCONV.push_back(in1);
            forCONV.push_back(out1);
        }   
        for (int j = 0; j < sz(pr[e2]); j++)
        {
            int in1=tin[pr[e2][j]], out1=out[pr[e2][j]];
            forCONV.push_back(in1);
            forCONV.push_back(out1);
        }
        sort(all(forCONV));
        for (int j = 0; j < sz(forCONV); j++)
        {
            conv2[forCONV[j]]=j;
        }
        
        for (int j = 0; j < sz(pr[e1]); j++)
        {
            int in1=tin[pr[e1][j]], out1=out[pr[e1][j]];
            tos.push_back({conv2[in1],{conv2[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({conv2[in1],{conv2[out1],2}});
        }
        sort(all(tos));
        vector<int> t;
        t.resize(sz(forCONV)*2+1,0);
        int ones=0;
        for (int j = 0; j < sz(tos); j++)
        {
            if(tos[j].second.second==1) {
                ones++;
                int p=tos[j].second.first;
                int value=1;
                for (t[p += sz(forCONV)] = value; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1];
            }
            else{
                int csum=0;
                int l=0;
                int r=tos[j].second.first+1;
                for (l += sz(forCONV), r += sz(forCONV); l < r; l >>= 1, r >>= 1) {
                    if (l&1) csum += t[l++];
                    if (r&1) csum += t[--r];
                }
                sm+=ones-csum;
            }
        }
        cout << sm << endl;
    }
    
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 4 ms 600 KB Output is correct
5 Correct 10 ms 856 KB Output is correct
6 Correct 19 ms 3160 KB Output is correct
7 Correct 36 ms 1368 KB Output is correct
8 Correct 51 ms 1980 KB Output is correct
9 Correct 107 ms 12388 KB Output is correct
10 Correct 194 ms 3264 KB Output is correct
11 Correct 424 ms 3988 KB Output is correct
12 Correct 523 ms 12984 KB Output is correct
13 Correct 699 ms 3416 KB Output is correct
14 Correct 1387 ms 3876 KB Output is correct
15 Correct 1784 ms 88372 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8005 ms 37796 KB Time limit exceeded
2 Execution timed out 8022 ms 10628 KB Time limit exceeded
3 Execution timed out 8029 ms 81432 KB Time limit exceeded
4 Correct 1127 ms 22296 KB Output is correct
5 Correct 1266 ms 76536 KB Output is correct
6 Correct 7080 ms 44200 KB Output is correct
7 Execution timed out 8057 ms 56196 KB Time limit exceeded
8 Runtime error 316 ms 131072 KB Execution killed with signal 9
9 Execution timed out 8095 ms 111752 KB Time limit exceeded
10 Runtime error 129 ms 131072 KB Execution killed with signal 9
11 Execution timed out 8031 ms 121052 KB Time limit exceeded
12 Execution timed out 8105 ms 87072 KB Time limit exceeded
13 Execution timed out 8026 ms 119364 KB Time limit exceeded
14 Execution timed out 8102 ms 112180 KB Time limit exceeded
15 Runtime error 94 ms 131072 KB Execution killed with signal 9
16 Runtime error 105 ms 131072 KB Execution killed with signal 9
17 Runtime error 163 ms 131072 KB Execution killed with signal 9