oj.uz

답안 #390004

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390004 2021-04-15T04:46:41 Z arwaeystoamneg Regions (IOI09_regions) C++17
90 / 100
 8000 ms 39608 KB 
// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#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 trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
//#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
}

const int MAX = 2e5 + 3, MAXK = 25e3 + 5;
vi adj[MAX], c[MAXK], d[MAXK];
int n, k, q, a[MAX], sizes[MAX], po = 0, tin[MAX], timenow;
void dfs(int i, int p = -1)
{
	c[a[i]].pb(i);
	tin[i] = timenow++;
	sizes[i] = 1;
	trav(x, adj[i])
	{
		if (x == p)continue;
		dfs(x, i);
		sizes[i] += sizes[x];
	}
}
map<int, int>ans[MAXK];

int main()
{
	setIO("");
	cin >> n >> k >> q;
	cin >> a[0];
	a[0]--;
	FOR(i, 1, n)
	{
		int p;
		cin >> p;
		adj[i].pb(--p);
		adj[p].pb(i);
		cin >> a[i];
		a[i]--;
	}
	dfs(0);
	int sq = 450;
	F0R(i, k)
	{
		trav(x, c[i])d[i].pb(tin[x]);
	}
	while (q--)
	{
		int x, y;
		cin >> x >> y;
		x--, y--;
		if (ans[x].find(y) != ans[x].end())
		{
			cout << ans[x][y] << endl;
		}/*
		else if (sz(c[y]) < sq)
		{
			int res = 0;
			trav(t, c[y])
			{
				res += upper_bound(all(d[x]), tin[t] + sizes[t] - 1) - lower_bound(all(d[x]), tin[t]);
			}
			ans[y][x] = res;
			cout << sz(c[x]) * sz(c[y]) - res << endl;
		}*/
		else
		{
			int res = 0;
			trav(t, c[x])
			{
				res += upper_bound(all(d[y]), tin[t] + sizes[t] - 1) - lower_bound(all(d[y]), tin[t]);
			}
			ans[x][y] = res;
			cout << res << endl;
		}
	}

}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:87:6: warning: unused variable 'sq' [-Wunused-variable]
   87 |  int sq = 450;
      |      ^~
regions.cpp: In function 'void setIO(std::string)':
regions.cpp:48:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:50:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   50 |    freopen((s + ".out").c_str(), "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7368 KB Output is correct
2 Correct 5 ms 7368 KB Output is correct
3 Correct 6 ms 7376 KB Output is correct
4 Correct 11 ms 7392 KB Output is correct
5 Correct 14 ms 7368 KB Output is correct
6 Correct 31 ms 7492 KB Output is correct
7 Correct 43 ms 7500 KB Output is correct
8 Correct 35 ms 7544 KB Output is correct
9 Correct 47 ms 8172 KB Output is correct
10 Correct 114 ms 8264 KB Output is correct
11 Correct 164 ms 8628 KB Output is correct
12 Correct 128 ms 9240 KB Output is correct
13 Correct 211 ms 9268 KB Output is correct
14 Correct 266 ms 9668 KB Output is correct
15 Correct 361 ms 12760 KB Output is correct

Subtask #2
75.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1814 ms 13676 KB Output is correct
2 Correct 1901 ms 13128 KB Output is correct
3 Correct 3120 ms 17292 KB Output is correct
4 Correct 368 ms 10360 KB Output is correct
5 Correct 417 ms 12608 KB Output is correct
6 Correct 756 ms 12112 KB Output is correct
7 Correct 1204 ms 12816 KB Output is correct
8 Correct 1555 ms 20400 KB Output is correct
9 Correct 2657 ms 23608 KB Output is correct
10 Correct 5173 ms 30700 KB Output is correct
11 Correct 5098 ms 28596 KB Output is correct
12 Correct 5695 ms 21932 KB Output is correct
13 Correct 6613 ms 24576 KB Output is correct
14 Execution timed out 8090 ms 25388 KB Time limit exceeded
15 Execution timed out 8082 ms 31400 KB Time limit exceeded
16 Correct 7561 ms 39608 KB Output is correct
17 Correct 6609 ms 37572 KB Output is correct