| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 162763 |
2019-11-09T16:03:33 Z |
faremy |
Regions (IOI09_regions) |
C++14 |
|
4016 ms |
42580 KB |
#include <iostream>
#include <algorithm>
#include <vector>
const int MAXN = 2e5;
const int MAXR = 25e3;
const int SQRTN = 450;
std::vector<int> tree[MAXN];
int color[MAXN];
int ofColor[MAXR];
int dfsPre[MAXN], dfsPost[MAXN];
int order[MAXR], revOrder[MAXR];
int ofNewColor[MAXR];
long long onOfColor[MAXR];
std::vector<long long> ancestersOfColor[MAXR];
std::vector<int> intervalStarts[MAXR];
std::vector<int> intervalEnds[MAXR];
int analysetree(int node, int seen)
{
ofColor[color[node]]++;
dfsPre[node] = seen;
int subseen = 1;
for (int child : tree[node])
subseen += analysetree(child, seen + subseen);
dfsPost[node] = seen + subseen;
return (subseen + 1);
}
void recolor(int colors, int nodes)
{
for (int iColor = 0; iColor < colors; iColor++)
order[iColor] = iColor;
std::sort(order, order + colors, [](int a, int b) { return (ofColor[a] > ofColor[b]); });
for (int iColor = 0; iColor < colors; iColor++)
ofNewColor[iColor] = ofColor[order[iColor]];
for (int iColor = 0; iColor < colors; iColor++)
ofColor[iColor] = ofNewColor[iColor];
for (int iColor = 0; iColor < colors; iColor++)
revOrder[order[iColor]] = iColor;
for (int iNode = 0; iNode < nodes; iNode++)
color[iNode] = revOrder[color[iNode]];
}
void buildpartialanswers(int node, int colors, int bigColors)
{
if (color[node] < bigColors)
for (int iColor = 0; iColor < colors; iColor++)
ancestersOfColor[color[node]][iColor] += onOfColor[iColor];
else
for (int iColor = 0; iColor < bigColors; iColor++)
ancestersOfColor[color[node]][iColor] += onOfColor[iColor];
intervalStarts[color[node]].emplace_back(dfsPre[node]);
intervalEnds[color[node]].emplace_back(dfsPost[node]);
onOfColor[color[node]]++;
for (int child : tree[node])
buildpartialanswers(child, colors, bigColors);
onOfColor[color[node]]--;
}
long long countbyfusion(int ancCol, int descCol)
{
int iAnc = 0, maxEnd = -1;
int ancesterPairs = 0;
for (int iDesc = 0; iDesc < ofColor[descCol]; iDesc++)
{
for (; iAnc < ofColor[ancCol] && intervalStarts[ancCol][iAnc] < intervalStarts[descCol][iDesc]; iAnc++)
maxEnd = std::max(maxEnd, intervalEnds[ancCol][iAnc]);
ancesterPairs += (maxEnd > intervalEnds[descCol][iDesc]);
}
return ancesterPairs;
}
int main()
{
int nodes, colors, queries;
std::cin >> nodes >> colors >> queries;
for (int iNode = 0; iNode < nodes; iNode++)
{
if (iNode > 0)
{
int parent; std::cin >> parent;
tree[parent - 1].emplace_back(iNode);
}
std::cin >> color[iNode];
color[iNode]--;
}
analysetree(0, 0);
recolor(colors, nodes);
int bigColors = 0;
while (bigColors < colors && ofColor[bigColors] > SQRTN)
bigColors++;
for (int iColor = 0; iColor < colors; iColor++)
{
if (iColor < bigColors)
ancestersOfColor[iColor].resize(colors, 0);
else
ancestersOfColor[iColor].resize(bigColors, 0);
}
buildpartialanswers(0, colors, bigColors);
for (int iQuery = 0; iQuery < queries; iQuery++)
{
int ancCol, descCol;
std::cin >> ancCol >> descCol;
ancCol = revOrder[ancCol - 1];
descCol = revOrder[descCol - 1];
if (descCol < bigColors || ancCol < bigColors)
std::cout << ancestersOfColor[descCol][ancCol] << std::endl;
else
std::cout << countbyfusion(ancCol, descCol) << std::endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6776 KB |
Output isn't correct |
| 2 |
Incorrect |
8 ms |
6696 KB |
Output isn't correct |
| 3 |
Incorrect |
10 ms |
6776 KB |
Output isn't correct |
| 4 |
Incorrect |
10 ms |
6776 KB |
Output isn't correct |
| 5 |
Incorrect |
16 ms |
6824 KB |
Output isn't correct |
| 6 |
Incorrect |
31 ms |
6904 KB |
Output isn't correct |
| 7 |
Incorrect |
40 ms |
6776 KB |
Output isn't correct |
| 8 |
Incorrect |
30 ms |
6960 KB |
Output isn't correct |
| 9 |
Incorrect |
50 ms |
7296 KB |
Output isn't correct |
| 10 |
Incorrect |
85 ms |
7336 KB |
Output isn't correct |
| 11 |
Incorrect |
129 ms |
7544 KB |
Output isn't correct |
| 12 |
Incorrect |
124 ms |
8072 KB |
Output isn't correct |
| 13 |
Incorrect |
186 ms |
7772 KB |
Output isn't correct |
| 14 |
Incorrect |
218 ms |
8312 KB |
Output isn't correct |
| 15 |
Incorrect |
216 ms |
10896 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1044 ms |
11516 KB |
Output isn't correct |
| 2 |
Incorrect |
1178 ms |
10232 KB |
Output isn't correct |
| 3 |
Incorrect |
1794 ms |
13308 KB |
Output isn't correct |
| 4 |
Incorrect |
268 ms |
8488 KB |
Output isn't correct |
| 5 |
Incorrect |
339 ms |
10152 KB |
Output isn't correct |
| 6 |
Incorrect |
929 ms |
16496 KB |
Output isn't correct |
| 7 |
Incorrect |
1084 ms |
13168 KB |
Output isn't correct |
| 8 |
Incorrect |
1531 ms |
31808 KB |
Output isn't correct |
| 9 |
Incorrect |
1900 ms |
16564 KB |
Output isn't correct |
| 10 |
Incorrect |
3080 ms |
42580 KB |
Output isn't correct |
| 11 |
Incorrect |
3178 ms |
16500 KB |
Output isn't correct |
| 12 |
Incorrect |
1903 ms |
18672 KB |
Output isn't correct |
| 13 |
Incorrect |
2148 ms |
18808 KB |
Output isn't correct |
| 14 |
Incorrect |
3045 ms |
25296 KB |
Output isn't correct |
| 15 |
Incorrect |
3477 ms |
23808 KB |
Output isn't correct |
| 16 |
Incorrect |
3532 ms |
28948 KB |
Output isn't correct |
| 17 |
Incorrect |
4016 ms |
33908 KB |
Output isn't correct |
