Submission #293343

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
293343	2020-09-07 22:59:53	Plurm	Regions (IOI09_regions)	C++11	100 / 100	5546 ms	117588 KiB

regions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int K = 2000;
vector<int> sp; // special regions
vector<int> bckt[25005];
int h[200005];
int s[200005];
int stat[200005][200005/K+10];
int cnt[200005]; // how many parents with i-th region
vector<int> g[200005];
int prec[200005/K+10][25005]; // prec[i][j] -> how the i-th special regions manage ones from j-th region
vector<int> et;
vector<int> etbckt[25005];
int st[200005];
int ft[200005];
void dfs(int u){
  st[u] = et.size();
  etbckt[h[u]].push_back(et.size());
  et.push_back(u);
  for(int i = 0; i < sp.size(); i++){
    stat[u][i] = cnt[sp[i]];
  }
  cnt[h[u]]++;
  for(int v : g[u]){
    dfs(v);
  }
  cnt[h[u]]--;
  ft[u] = et.size();
}
int query(int r1, int r2){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

regions.cpp: In function 'void dfs(int)':
regions.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i = 0; i < sp.size(); i++){
      |                 ~~^~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |    for(int j = 0; j < sp.size(); j++){
      |                   ~~^~~~~~~~~~~
regions.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |  scanf("%d%d%d",&n,&r,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |  scanf("%d", h+1);
      |  ~~~~~^~~~~~~~~~~
regions.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%d%d", s+i, h+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |   scanf("%d%d",&r1,&r2);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85