oj.uz

Submission #1051027

# Submission time Handle Problem Language Result Execution time Memory
1051027 2024-08-09T18:32:15 Z Ludissey Regions (IOI09_regions) C++17
75 / 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=sqrt(R);
    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--;
        if(conv[e1]<sq){
            sm=up[conv[e2]][conv[e1]];
        }else if(conv[e2]<sq) {
            sm=down[conv[e1]][conv[e2]];
        }else{

            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 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 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 14 ms 600 KB Output is correct
7 Correct 29 ms 600 KB Output is correct
8 Correct 32 ms 600 KB Output is correct
9 Correct 52 ms 1880 KB Output is correct
10 Correct 112 ms 1368 KB Output is correct
11 Correct 266 ms 1624 KB Output is correct
12 Correct 303 ms 3052 KB Output is correct
13 Correct 499 ms 1880 KB Output is correct
14 Correct 1029 ms 2648 KB Output is correct
15 Correct 1288 ms 11752 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4390 ms 8848 KB Output is correct
2 Correct 4615 ms 6012 KB Output is correct
3 Execution timed out 8077 ms 14160 KB Time limit exceeded
4 Correct 499 ms 5788 KB Output is correct
5 Correct 608 ms 16812 KB Output is correct
6 Correct 464 ms 12312 KB Output is correct
7 Correct 860 ms 17268 KB Output is correct
8 Correct 1555 ms 53808 KB Output is correct
9 Correct 4549 ms 39436 KB Output is correct
10 Correct 5004 ms 114728 KB Output is correct
11 Execution timed out 8073 ms 49860 KB Time limit exceeded
12 Correct 3369 ms 34940 KB Output is correct
13 Correct 4978 ms 44344 KB Output is correct
14 Correct 4322 ms 45024 KB Output is correct
15 Execution timed out 8019 ms 102524 KB Time limit exceeded
16 Runtime error 222 ms 131072 KB Execution killed with signal 9
17 Runtime error 256 ms 131072 KB Execution killed with signal 9