| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 672228 | 2022-12-15T06:27:38 Z | Hanksburger | Regions (IOI09_regions) | C++17 | 2392 ms | 50944 KB |
#include <bits/stdc++.h>
using namespace std;
vector<int> child[200005], vec[25005], ans[25005][2], tmp;
vector<pair<int, pair<int, bool> > > tt[25005];
int a[200005][2], region[200005];
vector<pair<int, bool> > t;
void dfs(int u)
{
a[u][0]=t.size();
t.push_back({u, 0});
for (int v:child[u])
dfs(v);
a[u][1]=t.size();
t.push_back({u, 1});
}
int main()
{
int n, m, q;
cin >> n >> m >> q;
for (int i=1; i<=n; i++)
{
if (i>1)
{
int x;
cin >> x;
child[x].push_back(i);
}
cin >> region[i];
vec[region[i]].push_back(i);
}
dfs(1);
for (int i=1; i<=m; i++)
{
for (int u:vec[i])
{
tt[i].push_back({a[u][0], {u, 0}});
tt[i].push_back({a[u][1], {u, 1}});
}
sort(tt[i].begin(), tt[i].end());
}
for (int i=1; i<=m; i++)
{
if (vec[i].size()*vec[i].size()>n)
{
for (int j=0; j<=m; j++)
{
ans[i][0].push_back(0);
ans[i][1].push_back(0);
}
int cur=0;
for (int j=0; j<t.size(); j++)
{
if (region[t[j].first]==i)
cur+=1-t[j].second*2;
else
ans[i][0][region[t[j].first]]+=cur*t[j].second;
}
tmp.clear();
for (int j=0; j<t.size(); j++)
{
if (region[t[j].first]==i)
cur+=t[j].second;
else if (t[j].second)
{
ans[i][1][region[tmp[tmp.size()-1]]]+=cur;
cur+=tmp[tmp.size()-2];
tmp.pop_back();
tmp.pop_back();
}
else
{
tmp.push_back(cur);
tmp.push_back(t[j].first);
cur=0;
}
}
}
}
for (int i=1; i<=q; i++)
{
int x, y;
cin >> x >> y;
if (vec[x].size()*vec[x].size()>n)
cout << ans[x][0][y] << '\n';
else if (vec[y].size()*vec[y].size()>n)
cout << ans[y][1][x] << '\n';
else
{
int cur=0, ind=0, res=0;
for (int j=0; j<tt[x].size(); j++)
{
while (ind<tt[y].size() && tt[y][ind].first<tt[x][j].first)
res+=cur*tt[y][ind++].second.second;
cur+=1-tt[x][j].second.second*2;
}
while (ind<tt[y].size())
res+=cur*tt[y][ind++].second.second;
cout << res << '\n';
}
fflush(stdout);
}
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 4 ms | 7248 KB | Output is correct |
| 2 | Correct | 4 ms | 7248 KB | Output is correct |
| 3 | Correct | 5 ms | 7248 KB | Output is correct |
| 4 | Correct | 9 ms | 7248 KB | Output is correct |
| 5 | Correct | 10 ms | 7376 KB | Output is correct |
| 6 | Correct | 24 ms | 7376 KB | Output is correct |
| 7 | Correct | 28 ms | 7504 KB | Output is correct |
| 8 | Correct | 29 ms | 7504 KB | Output is correct |
| 9 | Correct | 54 ms | 8144 KB | Output is correct |
| 10 | Correct | 84 ms | 8272 KB | Output is correct |
| 11 | Correct | 109 ms | 8724 KB | Output is correct |
| 12 | Correct | 117 ms | 9536 KB | Output is correct |
| 13 | Correct | 128 ms | 9468 KB | Output is correct |
| 14 | Correct | 199 ms | 10392 KB | Output is correct |
| 15 | Correct | 261 ms | 14680 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 727 ms | 15408 KB | Output is correct |
| 2 | Correct | 1043 ms | 14008 KB | Output is correct |
| 3 | Correct | 1407 ms | 18500 KB | Output is correct |
| 4 | Correct | 151 ms | 10344 KB | Output is correct |
| 5 | Correct | 232 ms | 12508 KB | Output is correct |
| 6 | Correct | 681 ms | 16164 KB | Output is correct |
| 7 | Correct | 838 ms | 18456 KB | Output is correct |
| 8 | Correct | 1050 ms | 30900 KB | Output is correct |
| 9 | Correct | 1591 ms | 23624 KB | Output is correct |
| 10 | Correct | 2123 ms | 50944 KB | Output is correct |
| 11 | Correct | 2277 ms | 24312 KB | Output is correct |
| 12 | Correct | 968 ms | 25728 KB | Output is correct |
| 13 | Correct | 1331 ms | 26248 KB | Output is correct |
| 14 | Correct | 1604 ms | 30100 KB | Output is correct |
| 15 | Correct | 2234 ms | 32216 KB | Output is correct |
| 16 | Correct | 2392 ms | 41308 KB | Output is correct |
| 17 | Correct | 2260 ms | 42968 KB | Output is correct |