oj.uz

답안 #722470

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
722470 2023-04-12T03:44:44 Z ono_de206 Regions (IOI09_regions) C++14
100 / 100
 4098 ms 31268 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
	out << c.first << ' ' << c.second;
    return out;
}

template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
	const int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) out << ' ';
		out << v[i];
	}
    return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
	for (T &x : v) in >> x;
    return in;
}


template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 2e5 + 10, B = 400;
int cnt[610][25010], in[mxn], out[mxn], tt, kk[25010], s[mxn], h[mxn];
vector<int> g[mxn], p[25010], d[25010];

void dfs(int to) {
	in[to] = ++tt;
	d[h[to]].pb(in[to]);
	for(int x : g[to]) {
		dfs(x);
	}
	out[to] = tt;
}

void solve(int to, int cn, int id) {
	if (kk[id] > 600) exit(1);
	cnt[kk[id]][h[to]] += cn;
	cn += (h[to] == id);
	for(int x : g[to]) {
		solve(x, cn, id);
	}
	cn -= (h[to] == id);
}

void go() {
	int n, r, q;
	// cin >> n >> r >> q;
	scanf("%d %d %d", &n, &r, &q);
	for(int i = 1; i<= n; i++) {
		if(i == 1)
			scanf("%d", &h[i]); // cin >> h[i];
		else
			scanf("%d %d", &s[i], &h[i]); // cin >> s[i] >> h[i];
		p[h[i]].pb(i);
		if(i > 1) g[s[i]].pb(i);
	}
	dfs(1);
	tt = 0;
	for(int i = 1; i <= r; i++) {
		if(p[i].size() >= B) {
			kk[i] = ++tt;
			solve(1, 0, i);
		}
		sort(all(d[i]));
	}
	while(q--) {
		int r1, r2;
		// cin >> r1 >> r2;
		scanf("%d %d", &r1, &r2);
		if(p[r1].size() >= B) {
			// cout << cnt[kk[r1]][r2] << '\n';
			printf("%d\n", cnt[kk[r1]][r2]);
		}
		else {
			int ans = 0;
			for(int x : p[r1]) {
				int ll = lower_bound(all(d[r2]), in[x]) - d[r2].begin();
				int rr = upper_bound(all(d[r2]), out[x]) - d[r2].begin();
				ans += rr - ll;
			}
			// cout << ans << '\n';
			printf("%d\n", ans);
		}
		fflush(stdout);
		// cout.flush();
	}
}
 
signed main() {
	// #ifndef
	// freopen("file.in", "r", stdin);
	// freopen("file.out", "w", stdout);
	// #endif
	// fast;
	int t = 1;
	// cin >> t;
	while(t--) {
		go();
	}
	return 0;
}

Compilation message

regions.cpp: In function 'void go()':
regions.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%d %d %d", &n, &r, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:78:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |    scanf("%d", &h[i]); // cin >> h[i];
      |    ~~~~~^~~~~~~~~~~~~
regions.cpp:80:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |    scanf("%d %d", &s[i], &h[i]); // cin >> s[i] >> h[i];
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d %d", &r1, &r2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6096 KB Output is correct
2 Correct 4 ms 6096 KB Output is correct
3 Correct 5 ms 6096 KB Output is correct
4 Correct 7 ms 6096 KB Output is correct
5 Correct 6 ms 6192 KB Output is correct
6 Correct 11 ms 6224 KB Output is correct
7 Correct 32 ms 6224 KB Output is correct
8 Correct 42 ms 6224 KB Output is correct
9 Correct 60 ms 6608 KB Output is correct
10 Correct 81 ms 6736 KB Output is correct
11 Correct 127 ms 6992 KB Output is correct
12 Correct 170 ms 7556 KB Output is correct
13 Correct 129 ms 7248 KB Output is correct
14 Correct 285 ms 7844 KB Output is correct
15 Correct 287 ms 9800 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1668 ms 11200 KB Output is correct
2 Correct 2336 ms 9976 KB Output is correct
3 Correct 2425 ms 12968 KB Output is correct
4 Correct 280 ms 7888 KB Output is correct
5 Correct 388 ms 9168 KB Output is correct
6 Correct 578 ms 11212 KB Output is correct
7 Correct 1297 ms 11624 KB Output is correct
8 Correct 1026 ms 19788 KB Output is correct
9 Correct 2516 ms 15860 KB Output is correct
10 Correct 3055 ms 31268 KB Output is correct
11 Correct 4098 ms 16168 KB Output is correct
12 Correct 1221 ms 17804 KB Output is correct
13 Correct 1852 ms 17996 KB Output is correct
14 Correct 2664 ms 19544 KB Output is correct
15 Correct 3059 ms 22276 KB Output is correct
16 Correct 2634 ms 27544 KB Output is correct
17 Correct 3101 ms 27980 KB Output is correct