oj.uz

Submission #527928

# Submission time Handle Problem Language Result Execution time Memory
527928 2022-02-18T18:32:29 Z MohamedAliSaidane Regions (IOI09_regions) C++14
30 / 100
 1140 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<pld> vpd;

#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(v) (v).begin(),(v).end()
#define ff first
#define ss second

const ll MOD = 1e9 + 7;
const ll INF = 1e18;
int nx[4] = {1,-1,0,0}, ny[4] = {0,0,1,-1};
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a, ll b){return (a / gcd(a, b)) * b;}


const int MAX_R = 504;
const int MAX_N =2e5 + 4;
ll sup[MAX_R][MAX_R];
int reg[MAX_N];
vi adj[MAX_N];
int n, r, q;
int p[MAX_N];
vi last;
void dfs(int x)
{
    vi cur;
    cur.assign(r,0);
    for(auto e: adj[x])
    {
        dfs(e);
        for(int h = 1; h <= r;h ++)
        {
            cur[h-1] += last[h-1] + (reg[e] == h);
        }
    }
    for(int h = 1; h <= r;h ++)
        sup[reg[x]][h] += cur[h-1];
    swap(cur,last);
    return;
}

void solve()
{
    cin >> n >> r >> q;
    cin >> reg[1];
    map<int,vi> m;
    m[reg[1]].pb(1);
    for(int i = 2; i <= n; i ++)
    {
        cin >> p[i] >> reg[i];
        adj[p[i]].pb(i);
        m[reg[i]].pb(i);
    }
    dfs(1);
    while(q--)
    {
        int u, v;
        cin >> u >> v;
        cout << sup[u][v] << endl;
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tt = 1;
    while(tt--)
        solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4936 KB Output is correct
2 Correct 3 ms 4936 KB Output is correct
3 Correct 5 ms 5064 KB Output is correct
4 Correct 8 ms 5064 KB Output is correct
5 Correct 11 ms 5192 KB Output is correct
6 Correct 20 ms 6856 KB Output is correct
7 Correct 30 ms 5704 KB Output is correct
8 Correct 34 ms 6088 KB Output is correct
9 Correct 39 ms 12320 KB Output is correct
10 Correct 61 ms 7368 KB Output is correct
11 Correct 113 ms 7440 KB Output is correct
12 Correct 143 ms 15912 KB Output is correct
13 Correct 159 ms 7112 KB Output is correct
14 Correct 78 ms 7312 KB Output is correct
15 Correct 193 ms 49060 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 21996 KB Output is correct
2 Correct 813 ms 10372 KB Output is correct
3 Correct 1140 ms 48816 KB Output is correct
4 Runtime error 25 ms 13712 KB Execution killed with signal 11
5 Runtime error 26 ms 19144 KB Execution killed with signal 11
6 Runtime error 26 ms 16584 KB Execution killed with signal 11
7 Runtime error 39 ms 23364 KB Execution killed with signal 11
8 Runtime error 81 ms 131076 KB Execution killed with signal 9
9 Runtime error 131 ms 65344 KB Execution killed with signal 11
10 Runtime error 118 ms 131076 KB Execution killed with signal 9
11 Runtime error 91 ms 29980 KB Execution killed with signal 11
12 Runtime error 105 ms 73920 KB Execution killed with signal 11
13 Runtime error 156 ms 88620 KB Execution killed with signal 11
14 Runtime error 91 ms 32372 KB Execution killed with signal 11
15 Runtime error 116 ms 131076 KB Execution killed with signal 9
16 Runtime error 121 ms 131076 KB Execution killed with signal 9
17 Runtime error 169 ms 120008 KB Execution killed with signal 11