oj.uz

Submission #525971

# Submission time Handle Problem Language Result Execution time Memory
525971 2022-02-13T11:06:08 Z idas Regions (IOI09_regions) C++11
70 / 100
 8000 ms 26436 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 << endl;
    }
}

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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6088 KB Output is correct
2 Correct 3 ms 6088 KB Output is correct
3 Correct 4 ms 6088 KB Output is correct
4 Correct 8 ms 6088 KB Output is correct
5 Correct 11 ms 6216 KB Output is correct
6 Correct 24 ms 6216 KB Output is correct
7 Correct 34 ms 6216 KB Output is correct
8 Correct 26 ms 6216 KB Output is correct
9 Correct 48 ms 6632 KB Output is correct
10 Correct 93 ms 6600 KB Output is correct
11 Correct 137 ms 6984 KB Output is correct
12 Correct 138 ms 7496 KB Output is correct
13 Correct 224 ms 7112 KB Output is correct
14 Correct 334 ms 7752 KB Output is correct
15 Correct 285 ms 10224 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8029 ms 10752 KB Time limit exceeded
2 Execution timed out 8012 ms 9544 KB Time limit exceeded
3 Execution timed out 8013 ms 12484 KB Time limit exceeded
4 Correct 315 ms 7752 KB Output is correct
5 Correct 381 ms 9416 KB Output is correct
6 Correct 1465 ms 8984 KB Output is correct
7 Correct 1924 ms 10040 KB Output is correct
8 Correct 1434 ms 15080 KB Output is correct
9 Correct 2599 ms 15512 KB Output is correct
10 Correct 4291 ms 20420 KB Output is correct
11 Correct 5641 ms 15296 KB Output is correct
12 Correct 6541 ms 16708 KB Output is correct
13 Correct 6541 ms 16960 KB Output is correct
14 Execution timed out 8054 ms 16672 KB Time limit exceeded
15 Execution timed out 8004 ms 21060 KB Time limit exceeded
16 Correct 7808 ms 26436 KB Output is correct
17 Execution timed out 8066 ms 25276 KB Time limit exceeded