제출 #978921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978921		AlphaMale06	Regions (IOI09_regions)	C++17	0 / 100	56 ms	25036 KiB

regions

#include <bits/stdc++.h>

using namespace std;

struct query{
    int a, b, ind, ans;
};

const int N = 2e5+3;

vector<int> g[N];
set<pair<int, int>> answered;
map<pair<int, int>, int> answer;
int a[N], tin[N], tout[N], cnt[N];
int f[2*N];
int timer=1;

void dfs(int v, int p){
    tin[v]=timer++;
    for(int to : g[v])dfs(to, v);
    tout[v]=timer++;
}

bool cmp(query A, query B){
    return A.a < B.a;
}

bool cmp2(query A, query B){
    return A.ind<B.ind;
}

void Update(int ind, int val){
    for(int i=ind; i<2*N; i+=i&-i)f[i]+=val;
}

int Get(int ind){
    int ret=0;
    for(int i=ind; i>0; i-=i&-i)ret+=f[i];
    return ret;
}

int Get(int l, int r){
    return Get(r)-Get(l-1);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, r, q;
    cin >> n >> r >> q;
    cin >> a[1];
    cnt[a[1]]++;
    for(int i=2; i<=n; i++){
        int x;
        cin >> x >> a[i];
        cnt[a[i]]++;
        g[x].push_back(i);
    }
    dfs(1, 1);
    vector<query> ups;
    vector<query> downs;
    for(int i=0; i<q; i++){
        int u, v;
        cin >> u >> v;
        if(cnt[u]>cnt[v])ups.push_back({u, v, i, 0});
        else downs.push_back({v, u, i, 0});
    }
    sort(downs.begin(), downs.end(), cmp);
    sort(ups.begin(), ups.end(), cmp);
    vector<int> pos[r+1];
    for(int i=1; i<=n; i++){
        pos[a[i]].push_back(i);
    }
    if(downs.size()){
        for(int e : pos[downs[0].a])Update(tin[e], 1);
        for(int e : pos[downs[0].b])downs[0].ans+=Get(tin[e], tout[e]);
        answered.insert({downs[0]. a, downs[0]. b});
        answer[{downs[0].a, downs[0].b}] = downs[0].ans;
        for(int i=1; i<downs.size(); i++){
            if(downs[i].a!=downs[i-1].a){
                for(int e : pos[downs[i-1].a])Update(tin[e], -1);
                for(int e : pos[downs[i].a])Update(tin[e], 1);
            }
            if(answered.find({downs[i].a, downs[i].b})!=answered.end()){
                downs[i].ans = answer[{downs[i].a, downs[i].b}];
                continue;
            }
            for(int e : pos[downs[i].b])downs[i].ans+=Get(tin[e], tout[e]);
            answered.insert({downs[i].a, downs[i].b});
            answer[{downs[i].a, downs[i].b}] = downs[i].ans;
        }
    }
    for(int i=0; i<2*N; i++)f[i]=0;
    answered.clear();
    answer.clear();
    if(ups.size()){
        for(int e : pos[ups[0].a]){
            Update(tin[e], 1);
            Update(tout[e], -1);
        }
        for(int e : pos[ups[0].b])ups[0].ans+=Get(0, tin[e]);
        answer[{ups[0].a, ups[0].b}] = ups[0].ans;
        answered.insert({ups[0].a, ups[0].b});
        for(int i=1; i<ups.size(); i++){
            if(ups[i].a!=ups[i-1].a){
                for(int e : pos[ups[i-1].a]){
                    Update(tin[e], -1);
                    Update(tout[e], 1);
                }
                for(int e : pos[ups[i].a]){
                    Update(tin[e], 1);
                    Update(tout[e], -1);
                }
            }
            if(answered.find({ups[i].a, ups[i].b})!=answered.end()){
                ups[i].ans=answer[{ups[i].a, ups[i].b}];
                continue;
            }
            for(int e : pos[ups[i].b])ups[i].ans+=Get(0, tin[e]);
            answer[{ups[i].a, ups[i].b}] = ups[i].ans;
            answered.insert({ups[i].a, ups[i].b});
        }
    }
    vector<query> svi;
    for(auto & e : downs)svi.push_back(e);
    for(auto & e : ups)svi.push_back(e);
    sort(svi.begin(), svi.end(), cmp2);
    for(auto & e : svi)cout << e.ans << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

regions.cpp: In function 'int main()':
regions.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int i=1; i<downs.size(); i++){
      |                      ~^~~~~~~~~~~~~
regions.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int i=1; i<ups.size(); i++){
      |                      ~^~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85