Submission #415752

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
415752	2021-06-01 13:01:31	Antekb	Regions (IOI09_regions)	C++14	100 / 100	4951 ms	130604 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 N=500, M=25000, K=200000;
vector<int> E[K];
int R[K], pre[K], post[K], ile3[M], sta[M], sta2[M];
vector<int> pocz[M], kon[M];
int ile[M][N], ile2[M][N], gdzie[M];
vector<int> duz;
int wsk=0;
void dfs(int v){
    //cout<<v<<"q\n";
    pre[v]=wsk++;
    pocz[R[v]].push_back(pre[v]);
    sta[R[v]]++;
    sta2[R[v]]++;
    for(int i=0; i<duz.size(); i++){
        ile[R[v]][i]-=sta[duz[i]];
        ile2[R[v]][i]+=sta2[duz[i]];
    }
    for(int u:E[v]){
        dfs(u);
    }
    for(int i=0; i<duz.size(); i++){
        ile[R[v]][i]+=sta[duz[i]];
    }
    sta2[R[v]]--;
    post[v]=wsk;
    kon[R[v]].push_back(post[v]);
}
int main(){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

regions.cpp: In function 'void dfs(int)':
regions.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=0; i<duz.size(); i++){
      |                  ~^~~~~~~~~~~
regions.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0; i<duz.size(); i++){
      |                  ~^~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:34:13: warning: unused variable 'h' [-Wunused-variable]
   34 |         int h, p;
      |             ^
regions.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for(int i=0; i<pocz[r1].size(); i++){
      |                          ~^~~~~~~~~~~~~~~~

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