답안 #939904

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939904 2024-03-06T23:36:49 Z idiotcomputer Regions (IOI09_regions) C++11
1 / 100
1380 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 < 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;
        for (int j = 0; j < all[b].sz(); j++){
            while (p.sz() > 0 && p.top() <= j){
                p.pop();
                c -= 1;
            }
            while (idx < all[a].sz() && all[a][idx] <= j){
                c += 1;
                idx++;
                p.push(first[all[a][idx]] + ssize[all[a][idx]]);
            }
            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:107:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |         if (all[a].sz() > gsize){
      |             ~~~~~~~~~~~~^~~~~~~
regions.cpp:111:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |         if (all[b].sz() > gsize){
      |             ~~~~~~~~~~~~^~~~~~~
regions.cpp:118:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for (int j = 0; j < all[b].sz(); j++){
      |                         ~~^~~~~~~~~~~~~
regions.cpp:123:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             while (idx < all[a].sz() && all[a][idx] <= j){
      |                    ~~~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Incorrect 2 ms 9816 KB Output isn't correct
3 Incorrect 3 ms 9816 KB Output isn't correct
4 Incorrect 4 ms 9816 KB Output isn't correct
5 Incorrect 6 ms 9816 KB Output isn't correct
6 Incorrect 11 ms 9816 KB Output isn't correct
7 Incorrect 13 ms 9816 KB Output isn't correct
8 Incorrect 17 ms 9816 KB Output isn't correct
9 Incorrect 24 ms 10328 KB Output isn't correct
10 Incorrect 43 ms 10328 KB Output isn't correct
11 Incorrect 50 ms 10504 KB Output isn't correct
12 Incorrect 72 ms 10840 KB Output isn't correct
13 Incorrect 89 ms 10812 KB Output isn't correct
14 Incorrect 108 ms 12760 KB Output isn't correct
15 Incorrect 123 ms 14868 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 487 ms 41144 KB Output isn't correct
2 Incorrect 584 ms 29900 KB Output isn't correct
3 Incorrect 819 ms 29984 KB Output isn't correct
4 Incorrect 184 ms 11244 KB Output isn't correct
5 Incorrect 246 ms 12980 KB Output isn't correct
6 Incorrect 343 ms 61660 KB Output isn't correct
7 Incorrect 545 ms 68304 KB Output isn't correct
8 Runtime error 140 ms 131072 KB Execution killed with signal 9
9 Incorrect 958 ms 17812 KB Output isn't correct
10 Runtime error 221 ms 131072 KB Execution killed with signal 9
11 Incorrect 1380 ms 18968 KB Output isn't correct
12 Incorrect 585 ms 24112 KB Output isn't correct
13 Incorrect 736 ms 25136 KB Output isn't correct
14 Incorrect 1002 ms 88008 KB Output isn't correct
15 Incorrect 1243 ms 29364 KB Output isn't correct
16 Incorrect 1321 ms 36668 KB Output isn't correct
17 Incorrect 1255 ms 100924 KB Output isn't correct