oj.uz

답안 #939907

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939907 2024-03-07T00:00:04 Z idiotcomputer Regions (IOI09_regions) C++11
100 / 100
 2338 ms 53004 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int 
#define sz size

const int mxN = 2e5;
const int mxR = 25*1e3;
int n,r;

vector<int> adj[mxN];
int reg[mxN];
vector<int> all[mxR];
int first[mxN];
int ssize[mxN];
vector<int> ord;

unordered_map<int,ll> cnts[mxR];
unordered_map<int,ll> rcnts[mxR];
int tarr[mxN+1];

void dfs(int node, int p){
    first[node] = ord.sz();
    all[reg[node]].pb(node);
    ord.pb(node);
    ssize[node] = 1;
    for (int next : adj[node]){
        if (next != p){
            dfs(next,node);
            ssize[node] += ssize[next];
        }
    }
}



int main()
{
   // ios_base::sync_with_stdio(false);
   // cin.tie(NULL);
    
    int q;
    cin >> n >> r >> q;
    int a,b;
    cin >> a;
    reg[0] = a-1;
    for (int i = 1; i < n; i++){
        cin >> b >> a;
        a -= 1;
        b -= 1;
        reg[i] = a;
        adj[i].pb(b);
        adj[b].pb(i);
    }
    
    dfs(0,-1);
    int gsize = (double) 2* sqrt(n);
    for (int i = 0; i < r; i++){
        if (all[i].sz() <= gsize){
            continue;
        }
     //   cnts[i].resize(n);
        memset(tarr,0,sizeof(tarr));
        for (int j =0; j < all[i].sz(); j++){
            tarr[first[all[i][j]]] += 1;
            tarr[first[all[i][j]] + ssize[all[i][j]]] -= 1;
        }
        for (int j = 0; j < n; j++){
            if (j > 0) tarr[j] += tarr[j-1];
            cnts[i][reg[ord[j]]] += tarr[j];
        }
     //   rcnts[i].resize(n);
        memset(tarr,0,sizeof(tarr));
        for (int j =0; j < all[i].sz(); j++){
            tarr[first[all[i][j]]] += 1;
        }
        for (int j = 1; j < n; j++){
            tarr[j] += tarr[j-1];
        }
        for (int j = 0; j < n; j++){
            rcnts[i][reg[ord[j]]] += tarr[j+ssize[ord[j]]-1] - tarr[j];
        }
    }
    /*cout << gsize<< " gsize\n";
    for (int i =0; i < r; i++){
        cout << all[i].sz() << ":\n";
        for (int j = 0; j < all[i].sz(); j++) cout << all[i][j] << " ";
        cout << '\n';
        if (all[i].sz() <= gsize){
            continue;
        }
        for (int j =0; j < n; j++){
            cout << cnts[i][j] << " ";
        }
        cout << '\n';
        for (int j = 0; j < n; j++) cout << rcnts[i][j] << " ";
        cout << '\n';
    }
    */
    int c,idx;
    stack<int> p;
    ll res;
  /*  for (int i =0; i <r; i++){
        cout << i << ": ";
        for (int j : all[i]){
            cout << first[j] << "-" << ssize[j] << " ";
        }
        cout << '\n';
    }*/
    for (int i =0; i < q; i++){
        cin >> a >> b;
        a -= 1;
        b -= 1;
        if (all[a].sz() > gsize){
            cout << cnts[a][b] << '\n';
            continue;
        }
        if (all[b].sz() > gsize){
            cout << rcnts[b][a] << "\n";
            continue;
        }
        c = 0;
        idx = 0;
        res = 0;
       // cout << a << "," << b << ": ";
        for (int j = 0; j < all[b].sz(); j++){
          //  cout << p.sz() << " " << idx << " " << all[a].sz() << '\n';
            while (p.sz() > 0 && p.top() <= first[all[b][j]]){
                p.pop();
           //     cout << "Rm\n";
                c -= 1;
            }
         //   cout << ";\n";
            while (idx < all[a].sz() && first[all[a][idx]] <= first[all[b][j]]){
                c += 1;
            //    cout << all[a][idx] << '\n';
                p.push(first[all[a][idx]] + ssize[all[a][idx]]);
                idx++;
                while (p.sz() > 0 && p.top() <= first[all[b][j]]){
                    p.pop();
                    c -= 1;
                }
            }
         //   cout << p.sz() << "l\n";
            
       //     cout << c << ' ' << p.top() << '\n';
    //   cout << c << '\n';
            res += c;
        }
        cout << res << '\n';
        while (p.sz() > 0){
            p.pop();
        }
    }
    
    
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:59:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |         if (all[i].sz() <= gsize){
      |             ~~~~~~~~~~~~^~~~~~~~
regions.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int j =0; j < all[i].sz(); j++){
      |                        ~~^~~~~~~~~~~~~
regions.cpp:74:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for (int j =0; j < all[i].sz(); j++){
      |                        ~~^~~~~~~~~~~~~
regions.cpp:114:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  114 |         if (all[a].sz() > gsize){
      |             ~~~~~~~~~~~~^~~~~~~
regions.cpp:118:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |         if (all[b].sz() > gsize){
      |             ~~~~~~~~~~~~^~~~~~~
regions.cpp:126:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for (int j = 0; j < all[b].sz(); j++){
      |                         ~~^~~~~~~~~~~~~
regions.cpp:134:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             while (idx < all[a].sz() && first[all[a][idx]] <= first[all[b][j]]){
      |                    ~~~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 11352 KB Output is correct
2 Correct 2 ms 11352 KB Output is correct
3 Correct 3 ms 11352 KB Output is correct
4 Correct 5 ms 11352 KB Output is correct
5 Correct 5 ms 11352 KB Output is correct
6 Correct 11 ms 11352 KB Output is correct
7 Correct 17 ms 11352 KB Output is correct
8 Correct 23 ms 11352 KB Output is correct
9 Correct 29 ms 11864 KB Output is correct
10 Correct 44 ms 12020 KB Output is correct
11 Correct 72 ms 12068 KB Output is correct
12 Correct 89 ms 12452 KB Output is correct
13 Correct 103 ms 12288 KB Output is correct
14 Correct 164 ms 12520 KB Output is correct
15 Correct 196 ms 15548 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 818 ms 15592 KB Output is correct
2 Correct 749 ms 15172 KB Output is correct
3 Correct 1393 ms 17524 KB Output is correct
4 Correct 195 ms 12700 KB Output is correct
5 Correct 237 ms 14460 KB Output is correct
6 Correct 464 ms 46740 KB Output is correct
7 Correct 889 ms 14992 KB Output is correct
8 Correct 919 ms 19748 KB Output is correct
9 Correct 1455 ms 19212 KB Output is correct
10 Correct 2311 ms 24372 KB Output is correct
11 Correct 2338 ms 20440 KB Output is correct
12 Correct 834 ms 21892 KB Output is correct
13 Correct 1188 ms 23108 KB Output is correct
14 Correct 1446 ms 41212 KB Output is correct
15 Correct 1929 ms 28808 KB Output is correct
16 Correct 1894 ms 36252 KB Output is correct
17 Correct 2001 ms 53004 KB Output is correct