oj.uz

답안 #907799

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
907799 2024-01-16T04:50:16 Z trMatherz Regions (IOI09_regions) C++17
21 / 100
 2240 ms 131072 KB 
#include <iostream> //cin, cout

/*
#include <fstream>
std::ifstream cin ("ex.in");
std::ofstream cout ("ex.out");
*/




// includes
#include <cmath> 
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>



//usings 
using namespace std;
using namespace __gnu_pbds;


// misc
#define ll long long
#define pb push_back
#define pq priority_queue
#define ub upper_bound
#define lb lower_bound
template<typename T, typename U> bool emin(T &a, const U &b){ return b < a ? a = b, true : false; }
template<typename T, typename U> bool emax(T &a, const U &b){ return b > a ? a = b, true : false; }
typedef uint64_t hash_t;

// vectors
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vpii vector<pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define vppipi vector<pair<int, pair<int, int>>>
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>
#define vpll vector<pair<ll, ll>>
#define vb vector<bool>
#define vvb vector<vb>
#define vs vector<string>
#define sz(x) (int)x.size()
#define rz resize
#define all(x) x.begin(), x.end()


// pairs
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define f first
#define s second

// sets
#define si set<int>
#define sl set<ll>
#define ss set<string>
#define in insert
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// maps
#define mii map<int, int>
#define mll map<ll, ll>

// loops
#define FR(x, z, y) for (int x = z; x < y; x++)
#define FRE(x, z, y) FR(x, z, y + 1)
#define F(x, y) FR(x, 0, y)
#define FE(x, y) F(x, y + 1)
#define A(x, y) for(auto &x : y)

int n, r, q;
vvi a;
vvi v;
vvi b;
vi c;
vi s, e;
int ct = 0;
vvi p;
int sr; 


void dfs(int x, mii cur){
    A(u, cur) p[u.f][c[x]]++;
    if(sz(v[c[x]]) >= sr){
        if(cur.find(c[x]) == cur.end()) cur[c[x]] = 1;
        else cur[c[x]]++;
    }
    s[x] = ct++;
    b[c[x]].pb(ct - 1);
    A(u, a[x]) dfs(u, cur);
    e[x] = ct - 1;
}
int main(){
    cin >> n >> r >> q;
    c = s = e = vi(n);
    p = vvi(r, vi(r, 0));
    a = vvi(n); v = b = vvi(r); cin >> c[0]; v[--c[0]].pb(0);
    FR(i, 1, n){int x; cin >> x; a[--x].pb(i); cin >> c[i]; v[--c[i]].pb(i);}
    sr = (int) sqrt(n);
    mii tempm;
    dfs(0, tempm);
    while(q--){
        int x, y; cin >> x >> y; x--; y--;
        int an = 0;
        if(sz(v[x]) < sr){
            A(u, v[x]){
                int w = e[u];
                int l = s[u];
                an += (ub(all(b[y]), w) - b[y].begin()) - (ub(all(b[y]), l) - b[y].begin());
            }
        } else {
            an = p[x][y];
        }
        cout << an << endl;
    }
    return 0;
}

Subtask #1
11.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 9 ms 856 KB Output is correct
7 Correct 13 ms 600 KB Output is correct
8 Correct 17 ms 600 KB Output is correct
9 Correct 24 ms 2132 KB Output is correct
10 Correct 45 ms 1880 KB Output is correct
11 Correct 84 ms 1876 KB Output is correct
12 Correct 97 ms 3416 KB Output is correct
13 Correct 130 ms 2496 KB Output is correct
14 Incorrect 239 ms 2880 KB Output isn't correct
15 Incorrect 225 ms 11548 KB Output isn't correct

Subtask #2
10.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1479 ms 24332 KB Output isn't correct
2 Incorrect 1720 ms 7196 KB Output isn't correct
3 Incorrect 2240 ms 28592 KB Output isn't correct
4 Correct 220 ms 65776 KB Output is correct
5 Correct 297 ms 105248 KB Output is correct
6 Runtime error 55 ms 131072 KB Execution killed with signal 9
7 Runtime error 58 ms 131072 KB Execution killed with signal 9
8 Runtime error 55 ms 131072 KB Execution killed with signal 9
9 Runtime error 55 ms 131072 KB Execution killed with signal 9
10 Runtime error 55 ms 131072 KB Execution killed with signal 9
11 Runtime error 56 ms 131072 KB Execution killed with signal 9
12 Runtime error 57 ms 131072 KB Execution killed with signal 9
13 Runtime error 55 ms 131072 KB Execution killed with signal 9
14 Runtime error 57 ms 131072 KB Execution killed with signal 9
15 Runtime error 56 ms 131072 KB Execution killed with signal 9
16 Runtime error 55 ms 131072 KB Execution killed with signal 9
17 Runtime error 53 ms 131072 KB Execution killed with signal 9