oj.uz

Submission #525969

# Submission time Handle Problem Language Result Execution time Memory
525969 2022-02-13T10:57:44 Z idas Regions (IOI09_regions) C++11
0 / 100
 80 ms 26432 KB 
#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr)
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
#define TSTS int ttt; cin >> ttt; while(ttt--) solve()
#define all(x) (x).begin(), (x).end()
#define le(vec) vec[vec.size()-1]
#define sz(x) ((int)((x).size()))
#define pb push_back
#define s second
#define f first

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int INF=1e9, MOD=1e9+7, mod=998244353;
const ll LINF=1e18;

void setIO()
{
    FAST_IO;
}

void setIO(string s)
{
    FAST_IO;
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int N=2e5+10, R=25010;
int n, r, q, t, rg[N], tin[N], tout[N];
vi ad[N], gr[R], st[R];

void build(int u)
{
    tout[u]=tin[u]=++t;
    for(auto x : ad[u]){
        build(x);
        tout[u]=max(tout[u], tout[x]);
    }
}

int main()
{
    setIO();
    cin >> n >> r >> q;
    cin >> rg[0];
    gr[rg[0]].pb(0);
    FOR(i, 1, n)
    {
        int x; cin >> x;
        x--; cin >> rg[i];
        gr[rg[i]].pb(i);
        ad[x].pb(i);
    }
    build(0);
    FOR(i, 1, r+1)
    {
        for(auto x : gr[i]){
            st[i].pb(tin[x]);
        }
        sort(all(st[i]));
    }
    while(q--){
        int r1, r2;
        cin >> r1 >> r2;
        ll ans=0;
        for(auto i : gr[r1]){
            int le=-1, ri=sz(st[r2])-1;
            while(le<ri){
                int m=(le+ri+1)/2;
                if(st[r2][m]>tout[i]) ri=m-1;
                else le=m;
            }

            int l0=0, r0=sz(st[r2]);
            while(l0<r0){
                int m0=(l0+r0)/2;
                if(st[r2][m0]<tin[i]) l0=m0+1;
                else r0=m0;
            }

            if(le!=-1&&l0!=sz(st[r2])){
                ans+=le-l0+1;
            }
        }
        cout << ans << '\n';
    }
}

Compilation message

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 6088 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 6088 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 6088 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 6120 KB Time limit exceeded (wall clock)
5 Execution timed out 4 ms 6216 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 6216 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 6216 KB Time limit exceeded (wall clock)
8 Execution timed out 5 ms 6216 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 6632 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 6600 KB Time limit exceeded (wall clock)
11 Execution timed out 7 ms 6984 KB Time limit exceeded (wall clock)
12 Execution timed out 11 ms 7496 KB Time limit exceeded (wall clock)
13 Execution timed out 9 ms 7112 KB Time limit exceeded (wall clock)
14 Execution timed out 11 ms 7752 KB Time limit exceeded (wall clock)
15 Execution timed out 12 ms 10184 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 28 ms 10688 KB Time limit exceeded (wall clock)
2 Execution timed out 24 ms 9536 KB Time limit exceeded (wall clock)
3 Execution timed out 25 ms 12480 KB Time limit exceeded (wall clock)
4 Execution timed out 13 ms 7752 KB Time limit exceeded (wall clock)
5 Execution timed out 12 ms 9436 KB Time limit exceeded (wall clock)
6 Execution timed out 20 ms 9056 KB Time limit exceeded (wall clock)
7 Execution timed out 24 ms 10028 KB Time limit exceeded (wall clock)
8 Execution timed out 32 ms 15120 KB Time limit exceeded (wall clock)
9 Execution timed out 53 ms 15552 KB Time limit exceeded (wall clock)
10 Execution timed out 52 ms 20416 KB Time limit exceeded (wall clock)
11 Execution timed out 69 ms 15328 KB Time limit exceeded (wall clock)
12 Execution timed out 74 ms 16708 KB Time limit exceeded (wall clock)
13 Execution timed out 66 ms 16960 KB Time limit exceeded (wall clock)
14 Execution timed out 77 ms 16672 KB Time limit exceeded (wall clock)
15 Execution timed out 80 ms 21124 KB Time limit exceeded (wall clock)
16 Execution timed out 64 ms 26432 KB Time limit exceeded (wall clock)
17 Execution timed out 65 ms 25188 KB Time limit exceeded (wall clock)