oj.uz

답안 #1051028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1051028 2024-08-09T18:32:25 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

# 결과 실행 시간 메모리 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 7 ms 344 KB Output is correct
6 Correct 14 ms 600 KB Output is correct
7 Correct 24 ms 600 KB Output is correct
8 Correct 32 ms 600 KB Output is correct
9 Correct 65 ms 1880 KB Output is correct
10 Correct 124 ms 1368 KB Output is correct
11 Correct 322 ms 1624 KB Output is correct
12 Correct 298 ms 2904 KB Output is correct
13 Correct 507 ms 2092 KB Output is correct
14 Correct 1066 ms 2648 KB Output is correct
15 Correct 1417 ms 11756 KB Output is correct

Subtask #2
60.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4604 ms 8848 KB Output is correct
2 Correct 4666 ms 6020 KB Output is correct
3 Execution timed out 8016 ms 14420 KB Time limit exceeded
4 Correct 484 ms 5876 KB Output is correct
5 Correct 621 ms 16996 KB Output is correct
6 Correct 437 ms 12356 KB Output is correct
7 Correct 812 ms 17256 KB Output is correct
8 Correct 1648 ms 53532 KB Output is correct
9 Correct 4445 ms 39352 KB Output is correct
10 Correct 4926 ms 114728 KB Output is correct
11 Execution timed out 8060 ms 49920 KB Time limit exceeded
12 Correct 3344 ms 34856 KB Output is correct
13 Correct 4970 ms 44240 KB Output is correct
14 Correct 4334 ms 45008 KB Output is correct
15 Execution timed out 8058 ms 102316 KB Time limit exceeded
16 Runtime error 206 ms 131072 KB Execution killed with signal 9
17 Runtime error 235 ms 131072 KB Execution killed with signal 9