oj.uz

답안 #939905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939905 2024-03-06T23:54:29 Z idiotcomputer Regions (IOI09_regions) C++11
90 / 100
 2442 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;

vector<ll> cnts[mxR];
vector<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 3 ms 9816 KB Output is correct
2 Correct 3 ms 9824 KB Output is correct
3 Correct 3 ms 9816 KB Output is correct
4 Correct 4 ms 9816 KB Output is correct
5 Correct 7 ms 9816 KB Output is correct
6 Correct 13 ms 9816 KB Output is correct
7 Correct 20 ms 9816 KB Output is correct
8 Correct 18 ms 9816 KB Output is correct
9 Correct 26 ms 10328 KB Output is correct
10 Correct 51 ms 10332 KB Output is correct
11 Correct 80 ms 10504 KB Output is correct
12 Correct 87 ms 10948 KB Output is correct
13 Correct 118 ms 10816 KB Output is correct
14 Correct 148 ms 12776 KB Output is correct
15 Correct 189 ms 14864 KB Output is correct

Subtask #2
75.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 705 ms 41132 KB Output is correct
2 Correct 842 ms 29888 KB Output is correct
3 Correct 1416 ms 29980 KB Output is correct
4 Correct 185 ms 11072 KB Output is correct
5 Correct 283 ms 13000 KB Output is correct
6 Correct 372 ms 61652 KB Output is correct
7 Correct 608 ms 68304 KB Output is correct
8 Runtime error 132 ms 131072 KB Execution killed with signal 9
9 Correct 1401 ms 17800 KB Output is correct
10 Runtime error 183 ms 131072 KB Execution killed with signal 9
11 Correct 2442 ms 18916 KB Output is correct
12 Correct 865 ms 24112 KB Output is correct
13 Correct 1122 ms 25136 KB Output is correct
14 Correct 1276 ms 88008 KB Output is correct
15 Correct 1924 ms 29368 KB Output is correct
16 Correct 1935 ms 36660 KB Output is correct
17 Correct 1861 ms 100924 KB Output is correct