oj.uz

답안 #390003

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390003 2021-04-15T04:46:15 Z arwaeystoamneg Regions (IOI09_regions) C++17
0 / 100
 110 ms 30656 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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4 ms 7364 KB Time limit exceeded (wall clock)
2 Execution timed out 4 ms 7240 KB Time limit exceeded (wall clock)
3 Execution timed out 5 ms 7320 KB Time limit exceeded (wall clock)
4 Execution timed out 4 ms 7424 KB Time limit exceeded (wall clock)
5 Execution timed out 4 ms 7368 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 7372 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 7368 KB Time limit exceeded (wall clock)
8 Execution timed out 5 ms 7496 KB Time limit exceeded (wall clock)
9 Execution timed out 6 ms 7880 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 7880 KB Time limit exceeded (wall clock)
11 Execution timed out 10 ms 8136 KB Time limit exceeded (wall clock)
12 Execution timed out 11 ms 8648 KB Time limit exceeded (wall clock)
13 Execution timed out 12 ms 8648 KB Time limit exceeded (wall clock)
14 Execution timed out 14 ms 9032 KB Time limit exceeded (wall clock)
15 Execution timed out 18 ms 12104 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 28 ms 12328 KB Time limit exceeded (wall clock)
2 Execution timed out 35 ms 11840 KB Time limit exceeded (wall clock)
3 Execution timed out 34 ms 14300 KB Time limit exceeded (wall clock)
4 Execution timed out 16 ms 9160 KB Time limit exceeded (wall clock)
5 Execution timed out 20 ms 10952 KB Time limit exceeded (wall clock)
6 Execution timed out 24 ms 10568 KB Time limit exceeded (wall clock)
7 Execution timed out 33 ms 11712 KB Time limit exceeded (wall clock)
8 Execution timed out 40 ms 17352 KB Time limit exceeded (wall clock)
9 Execution timed out 74 ms 17344 KB Time limit exceeded (wall clock)
10 Execution timed out 67 ms 23048 KB Time limit exceeded (wall clock)
11 Execution timed out 89 ms 19520 KB Time limit exceeded (wall clock)
12 Execution timed out 110 ms 17996 KB Time limit exceeded (wall clock)
13 Execution timed out 83 ms 19104 KB Time limit exceeded (wall clock)
14 Execution timed out 97 ms 19140 KB Time limit exceeded (wall clock)
15 Execution timed out 80 ms 23336 KB Time limit exceeded (wall clock)
16 Execution timed out 83 ms 30656 KB Time limit exceeded (wall clock)
17 Execution timed out 84 ms 29156 KB Time limit exceeded (wall clock)