oj.uz

답안 #1051638

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1051638 2024-08-10T08:45:54 Z Ludissey Regions (IOI09_regions) C++17
30 / 100
 8000 ms 124688 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);
    //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

# 결과 실행 시간 메모리 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 3 ms 600 KB Output is correct
5 Correct 7 ms 600 KB Output is correct
6 Correct 12 ms 1368 KB Output is correct
7 Correct 28 ms 1112 KB Output is correct
8 Correct 28 ms 1368 KB Output is correct
9 Correct 56 ms 2136 KB Output is correct
10 Correct 112 ms 2908 KB Output is correct
11 Correct 300 ms 2648 KB Output is correct
12 Correct 299 ms 3924 KB Output is correct
13 Correct 525 ms 3160 KB Output is correct
14 Correct 1182 ms 3416 KB Output is correct
15 Correct 1434 ms 5820 KB Output is correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8018 ms 10820 KB Time limit exceeded
2 Execution timed out 8034 ms 10052 KB Time limit exceeded
3 Execution timed out 8037 ms 12968 KB Time limit exceeded
4 Correct 914 ms 18776 KB Output is correct
5 Correct 808 ms 24296 KB Output is correct
6 Correct 6829 ms 32652 KB Output is correct
7 Execution timed out 8064 ms 46152 KB Time limit exceeded
8 Execution timed out 8096 ms 50888 KB Time limit exceeded
9 Execution timed out 8041 ms 73040 KB Time limit exceeded
10 Execution timed out 8013 ms 117516 KB Time limit exceeded
11 Execution timed out 8048 ms 114348 KB Time limit exceeded
12 Execution timed out 8013 ms 81752 KB Time limit exceeded
13 Execution timed out 8031 ms 81732 KB Time limit exceeded
14 Execution timed out 8100 ms 98796 KB Time limit exceeded
15 Execution timed out 8016 ms 121312 KB Time limit exceeded
16 Execution timed out 8090 ms 124688 KB Time limit exceeded
17 Execution timed out 8103 ms 105300 KB Time limit exceeded