oj.uz

Submission #563474

# Submission time Handle Problem Language Result Execution time Memory
563474 2022-05-17T10:03:21 Z Soul234 Regions (IOI09_regions) C++14
0 / 100
 395 ms 31948 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

const int BL = 447;
const int MX = 2e5+5, MXR = 25005;
int N, R, Q, typ[MX], _timer, IDs[MX], IDtour[MX], tin[MX], tout[MX];
ll preans[BL][MXR];
vi adj[MX], reg[MXR];

void Flat(int u, int p) {
    IDtour[tin[u] = ++_timer] = u;
    reg[typ[u]].pb(tin[u]);
    each(v, adj[u]) if(v!=p) Flat(v, u);
    tout[u] = _timer;
}

void dfs(int u, int p, int idx, int cnt) {
    if(typ[u] == idx) cnt++;
    else preans[IDs[idx]][typ[u]] += cnt;
    each(v, adj[u]) if(v != p) dfs(v, u, idx, cnt);
}

void solve() {
    cin>>N>>R>>Q;
    cin>>typ[1];
    FOR(i,2,N+1) {
        int p; cin>>p>>typ[i];
        adj[p].pb(i);
        adj[i].pb(p);
    }
    Flat(1,-1);
    _timer = 0;
    FOR(i,1,R+1) if(sz(reg[i]) > BL) {
        IDs[i] = _timer++;
        dfs(1, -1, i, 0);
    }
    while(Q-->0) {
        int r1, r2;
        cin>>r1>>r2;
        if(sz(reg[r1]) > BL) cout << preans[IDs[r1]][r2] << nl;
        else {
            ll ans = 0;
            each(p, reg[r1]) {
                int u = IDtour[p];
                ans += upper_bound(all(reg[r2]), tout[u]) - lower_bound(all(reg[r2]), tin[u]);
            }
            cout << ans << nl;
        }
    }
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 5584 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 5584 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 5584 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 5584 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 5584 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 5712 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 5712 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 5712 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 6096 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 6096 KB Time limit exceeded (wall clock)
11 Execution timed out 7 ms 6412 KB Time limit exceeded (wall clock)
12 Execution timed out 10 ms 6908 KB Time limit exceeded (wall clock)
13 Execution timed out 9 ms 6864 KB Time limit exceeded (wall clock)
14 Execution timed out 14 ms 7248 KB Time limit exceeded (wall clock)
15 Execution timed out 14 ms 9680 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 53 ms 10584 KB Time limit exceeded (wall clock)
2 Execution timed out 58 ms 10260 KB Time limit exceeded (wall clock)
3 Execution timed out 50 ms 12560 KB Time limit exceeded (wall clock)
4 Execution timed out 13 ms 7376 KB Time limit exceeded (wall clock)
5 Execution timed out 12 ms 8784 KB Time limit exceeded (wall clock)
6 Execution timed out 89 ms 12256 KB Time limit exceeded (wall clock)
7 Execution timed out 55 ms 11092 KB Time limit exceeded (wall clock)
8 Execution timed out 200 ms 23496 KB Time limit exceeded (wall clock)
9 Execution timed out 67 ms 14792 KB Time limit exceeded (wall clock)
10 Execution timed out 247 ms 31948 KB Time limit exceeded (wall clock)
11 Execution timed out 79 ms 17084 KB Time limit exceeded (wall clock)
12 Execution timed out 108 ms 16200 KB Time limit exceeded (wall clock)
13 Execution timed out 102 ms 17372 KB Time limit exceeded (wall clock)
14 Execution timed out 395 ms 20460 KB Time limit exceeded (wall clock)
15 Execution timed out 72 ms 21328 KB Time limit exceeded (wall clock)
16 Execution timed out 76 ms 28608 KB Time limit exceeded (wall clock)
17 Execution timed out 149 ms 30444 KB Time limit exceeded (wall clock)