Submission #964160

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
964160	2024-04-16 11:39:34	Trisanu_Das	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	151 ms	23268 KiB

catdog

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 "catdog.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define mp make_pair
#define pb push_back
const int inf=1e9+7;
int min(int a, int b){ return a>b?b:a;}
const int N=100050;
const int M=2*N;
struct Matrix
{
  int a[2][2];
  void init(){ a[0][0]=a[1][1]=0;a[1][0]=a[0][1]=inf;}
  Matrix(){ init();}
  Matrix operator * (Matrix b) const
  {
    Matrix c;
    int i,j,k,l;
    for(i=0;i<2;i++) for(j=0;j<2;j++)
    {
      c.a[i][j]=inf;
      for(k=0;k<2;k++) for(l=0;l<2;l++) c.a[i][j]=min(c.a[i][j],a[i][k]+b.a[l][j]+(k^l));
    }
    return c;
  }
} node[M];
int ls[M],rs[M],root[N],tsz;
void Set(int &c, int ss, int se, int qi, int a, int b)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

catdog.cpp: In function 'void Set(int&, int, int, int, int, int)':
catdog.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |  int mid=ss+se>>1;
      |          ~~^~~
catdog.cpp: In function 'void DFS(int, int)':
catdog.cpp:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i=0;i<E[u].size();i++) if(E[u][i]!=p) DFS(E[u][i],u),sz[u]+=sz[E[u][i]];
      |              ~^~~~~~~~~~~~
catdog.cpp: In function 'void HLD(int, int)':
catdog.cpp:59:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(i=0;i<E[u].size();i++) if(E[u][i]!=p && sz[HC]<sz[E[u][i]]) HC=E[u][i];
      |          ~^~~~~~~~~~~~
catdog.cpp:61:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(i=0;i<E[u].size();i++) if(E[u][i]!=p) HLD(E[u][i],u);
      |          ~^~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 30 / 30
• Subtask 3: 62 / 62