Submission #1169586

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1169586	2025-03-19 02:26:44	sleepntsheep	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	284 ms	21548 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 <cstdio>
#include <vector>
#include <algorithm>
#define N 111111
struct Mat{
  long long a[4]={0};
  friend Mat operator*(const Mat &a, const Mat &b) {
    Mat c;
    c.a[0] = std::min(a.a[0] + b.a[0], a.a[1] + b.a[2]);
    c.a[1] = std::min(a.a[0] + b.a[1], a.a[1] + b.a[3]);
    c.a[2] = std::min(a.a[2] + b.a[0], a.a[3] + b.a[2]);
    c.a[3] = std::min(a.a[2] + b.a[1], a.a[3] + b.a[3]);
    return c;
  }
};
struct LCT {
  struct{
    int c[2],pa;
    Mat val,prod;
  } t[N];
  int nrt(int v){return t[t[v].pa].c[0]==v||t[t[v].pa].c[1]==v;}
  void pushup(int v){
    if(!v)return;
    if(t[v].c[0]&&t[v].c[1])t[v].prod=t[t[v].c[1]].prod*t[v].val*t[t[v].c[0]].prod;
    else if(t[v].c[0])t[v].prod=t[v].val*t[t[v].c[0]].prod;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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