oj.uz

답안 #722469

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
722469 2023-04-12T03:38:45 Z ono_de206 Regions (IOI09_regions) C++14
35 / 100
 8000 ms 131072 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[510][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) {
	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[h[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:74:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  scanf("%d %d %d", &n, &r, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:77:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |    scanf("%d", &h[i]); // cin >> h[i];
      |    ~~~~~^~~~~~~~~~~~~
regions.cpp:79:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |    scanf("%d %d", &s[i], &h[i]); // cin >> s[i] >> h[i];
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   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 6 ms 6096 KB Output is correct
4 Correct 8 ms 6096 KB Output is correct
5 Correct 10 ms 6096 KB Output is correct
6 Correct 18 ms 6224 KB Output is correct
7 Correct 28 ms 6224 KB Output is correct
8 Correct 39 ms 6224 KB Output is correct
9 Correct 44 ms 6612 KB Output is correct
10 Correct 84 ms 6736 KB Output is correct
11 Correct 122 ms 6992 KB Output is correct
12 Correct 148 ms 7504 KB Output is correct
13 Correct 211 ms 7248 KB Output is correct
14 Correct 288 ms 7888 KB Output is correct
15 Correct 266 ms 9852 KB Output is correct

Subtask #2
20.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2073 ms 11548 KB Output isn't correct
2 Incorrect 2251 ms 10376 KB Output isn't correct
3 Incorrect 2549 ms 13552 KB Output isn't correct
4 Correct 272 ms 7888 KB Output is correct
5 Correct 370 ms 9168 KB Output is correct
6 Runtime error 636 ms 51088 KB Execution killed with signal 11
7 Runtime error 1084 ms 65620 KB Execution killed with signal 11
8 Runtime error 820 ms 76016 KB Execution killed with signal 11
9 Correct 2602 ms 15820 KB Output is correct
10 Runtime error 1809 ms 131072 KB Execution killed with signal 11
11 Correct 4797 ms 16092 KB Output is correct
12 Execution timed out 8023 ms 48020 KB Time limit exceeded
13 Runtime error 5578 ms 104680 KB Execution killed with signal 11
14 Runtime error 6935 ms 120628 KB Execution killed with signal 11
15 Runtime error 3787 ms 131072 KB Execution killed with signal 11
16 Runtime error 2337 ms 131072 KB Execution killed with signal 11
17 Runtime error 2170 ms 131072 KB Execution killed with signal 11