oj.uz

Submission #865384

# Submission time Handle Problem Language Result Execution time Memory
865384 2023-10-24T07:48:16 Z AtabayRajabli Regions (IOI09_regions) C++17
80 / 100
 8000 ms 38336 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// author : AtabeyR

#define pb          push_back
#define pii         pair<int, int>
#define pll         pair<ll, ll>
#define all(v)      v.begin(), v.end()
#define OPT         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define sec         second
#define fi          first
#define int         ll
#define print(k)    cerr << "Ans : "; cout << k << endl;
#define ins         insert
#define bpc         __builtin_popcountll
#define skip        continue
#define endll        '\n'
#define gcd(a, b)   __gcd(a, b)
#define lcm(a, b)   a*b / (__gcd(a, b))

typedef long long ll;
typedef unsigned long long ull;
const int oo = 0x3F3F3F3F;
const int ooo = 0x3F3F3F3F3F3F3F3FLL;
const int mod = 998244353;
const int sz = 2e5+5;
using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;

void open(string s, string f)
{
    freopen((s + ".txt").c_str(), "r", stdin);
    freopen((f + ".txt").c_str(), "w", stdout);
}

int n, r, Q, h[sz], tim = 1, used[sz];
vector<int> g[sz];
vector<pii> rg[sz];

void dfs(int v)
{
    int in = tim++;
    used[v] = 1;
    for(int i : g[v])if(!used[i])dfs(i);
    int out = tim++;
    rg[h[v]].pb({in, out});
}

void solve(int t)
{
    cin >> n >> r >> Q;

    cin >> h[1];
    for(int i = 2; i<=n; i++)
    {
        int u;
        cin >> u >> h[i];
        g[u].pb(i); 
    }

    dfs(1);
    for(int i = 1; i<=r; i++)sort(all(rg[i]));

    while(Q--)
    {
        int u, v;
        cin >> u >> v;

        int ans = 0;
        for(pii i : rg[u])
        {
            auto it1 = lower_bound(all(rg[v]), pii(i.fi, -ooo));
            auto it2 = upper_bound(all(rg[v]), pii(i.sec, -ooo));
            ans += it2 - it1;
        }

        cout << ans << endl;
    }
}

int32_t main()
{
    // open("in", "out");

    OPT
    int t = 1;
    //cin >> t;

    for(int i = 1; i<=t; i++)
        solve(i);
}

Compilation message

regions.cpp: In function 'void open(std::string, std::string)':
regions.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen((s + ".txt").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen((f + ".txt").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 4 ms 12888 KB Output is correct
5 Correct 5 ms 12888 KB Output is correct
6 Correct 10 ms 12888 KB Output is correct
7 Correct 14 ms 12888 KB Output is correct
8 Correct 18 ms 12888 KB Output is correct
9 Correct 21 ms 13400 KB Output is correct
10 Correct 41 ms 13400 KB Output is correct
11 Correct 66 ms 13808 KB Output is correct
12 Correct 80 ms 14200 KB Output is correct
13 Correct 103 ms 14096 KB Output is correct
14 Correct 169 ms 14680 KB Output is correct
15 Correct 184 ms 18436 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8087 ms 18152 KB Time limit exceeded
2 Execution timed out 8025 ms 16552 KB Time limit exceeded
3 Execution timed out 8063 ms 20364 KB Time limit exceeded
4 Correct 156 ms 14936 KB Output is correct
5 Correct 204 ms 16920 KB Output is correct
6 Correct 1060 ms 16040 KB Output is correct
7 Correct 1171 ms 16844 KB Output is correct
8 Correct 873 ms 23424 KB Output is correct
9 Correct 1571 ms 22880 KB Output is correct
10 Correct 3247 ms 29052 KB Output is correct
11 Correct 2821 ms 22216 KB Output is correct
12 Correct 3290 ms 23024 KB Output is correct
13 Correct 3922 ms 23904 KB Output is correct
14 Correct 5030 ms 23148 KB Output is correct
15 Correct 5997 ms 29212 KB Output is correct
16 Correct 6439 ms 38336 KB Output is correct
17 Execution timed out 8042 ms 36532 KB Time limit exceeded