Submission #238461

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
238461	2020-06-11 12:17:52	DodgeBallMan	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	1843 ms	40172 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 <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int INF = 1e9;
const int N = 1e5 + 10;
int n, par[N], rot[N], lev[N], col[N], sz[N], pos[N], dep[N];
pii pv[N];
vector<int> g[N];
struct node {
    vector<int> v;
    node() { 
        v = vector<int>( 4, INF );
        v[0] = v[3] = 0;
    }
    friend node operator+( const node &a, const node &b ) {
        node ret;
        ret.v = vector<int>( 4, INF );
        for( int i = 0 ; i < 4 ; i++ ) for( int j = 0 ; j < 4 ; j++ ) {
            int bit = ( i&2 ) + ( j&1 );
            int dif = ( i&1 ) != ( (j>>1)&1 );
            ret.v[bit] = min( ret.v[bit], a.v[i] + b.v[j] + dif );
        }
        return ret;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

catdog.cpp: In function 'node query(int, int, int, int, int)':
catdog.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
catdog.cpp: In function 'void update(int, std::pair<int, int>, int, int, int)':
catdog.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
catdog.cpp: In function 'void build(int, int, int)':
catdog.cpp:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~

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