oj.uz

답안 #939906

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939906 2024-03-06T23:56:52 Z idiotcomputer Regions (IOI09_regions) C++11
95 / 100
 2477 ms 131072 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 = 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 3 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 6 ms 11352 KB Output is correct
6 Correct 13 ms 11352 KB Output is correct
7 Correct 18 ms 11352 KB Output is correct
8 Correct 22 ms 11352 KB Output is correct
9 Correct 25 ms 11864 KB Output is correct
10 Correct 41 ms 11880 KB Output is correct
11 Correct 78 ms 12088 KB Output is correct
12 Correct 84 ms 12448 KB Output is correct
13 Correct 108 ms 12312 KB Output is correct
14 Correct 163 ms 12888 KB Output is correct
15 Correct 195 ms 15736 KB Output is correct

Subtask #2
80.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 712 ms 15912 KB Output is correct
2 Correct 798 ms 15216 KB Output is correct
3 Correct 1379 ms 17440 KB Output is correct
4 Correct 188 ms 12636 KB Output is correct
5 Correct 213 ms 14452 KB Output is correct
6 Correct 484 ms 46748 KB Output is correct
7 Correct 644 ms 54012 KB Output is correct
8 Correct 974 ms 98584 KB Output is correct
9 Correct 1512 ms 19356 KB Output is correct
10 Runtime error 516 ms 131072 KB Execution killed with signal 9
11 Correct 2477 ms 20492 KB Output is correct
12 Correct 853 ms 21940 KB Output is correct
13 Correct 1240 ms 22948 KB Output is correct
14 Correct 1462 ms 51112 KB Output is correct
15 Correct 1923 ms 28800 KB Output is correct
16 Correct 2091 ms 36384 KB Output is correct
17 Correct 1922 ms 62788 KB Output is correct