oj.uz

Submission #563481

# Submission time Handle Problem Language Result Execution time Memory
563481 2022-05-17T10:08:03 Z Soul234 Regions (IOI09_regions) C++14
100 / 100
 3880 ms 31932 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;
        }
        cout.flush();
    }
}

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 3 ms 5584 KB Output is correct
3 Correct 5 ms 5520 KB Output is correct
4 Correct 7 ms 5584 KB Output is correct
5 Correct 10 ms 5584 KB Output is correct
6 Correct 17 ms 5712 KB Output is correct
7 Correct 30 ms 5712 KB Output is correct
8 Correct 31 ms 5712 KB Output is correct
9 Correct 32 ms 6096 KB Output is correct
10 Correct 76 ms 6096 KB Output is correct
11 Correct 114 ms 6480 KB Output is correct
12 Correct 135 ms 6864 KB Output is correct
13 Correct 157 ms 6864 KB Output is correct
14 Correct 255 ms 7248 KB Output is correct
15 Correct 268 ms 9680 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1771 ms 10612 KB Output is correct
2 Correct 1759 ms 10160 KB Output is correct
3 Correct 2726 ms 12608 KB Output is correct
4 Correct 225 ms 7304 KB Output is correct
5 Correct 280 ms 8784 KB Output is correct
6 Correct 511 ms 12324 KB Output is correct
7 Correct 1272 ms 11104 KB Output is correct
8 Correct 889 ms 23496 KB Output is correct
9 Correct 1765 ms 14908 KB Output is correct
10 Correct 3172 ms 31932 KB Output is correct
11 Correct 3880 ms 17092 KB Output is correct
12 Correct 1207 ms 16248 KB Output is correct
13 Correct 1899 ms 17228 KB Output is correct
14 Correct 2296 ms 20588 KB Output is correct
15 Correct 2857 ms 21456 KB Output is correct
16 Correct 2824 ms 28724 KB Output is correct
17 Correct 2521 ms 30492 KB Output is correct