Submission #152135

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
152135	2019-09-06 15:08:20	arnold518	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	1006 ms	26356 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int INF = 1e6;
int N;
vector<int> adj[MAXN+10];
int sz[MAXN+10], par[MAXN+10], dep[MAXN+10];
int idx[MAXN+10], cnt=1, head[MAXN+10], tail[MAXN+10];
int A[MAXN+10], C[MAXN+10], D[MAXN+10];
struct Node
{
    int AA, AB, BA, BB;
    Node(int AA, int AB, int BA, int BB) : AA(AA), AB(AB), BA(BA), BB(BB) {}
    Node() : AA(0), AB(0), BA(0), BB(0) {}
};
Node combine(Node lc, Node rc)
{
    Node ret;
    ret.AA=min({lc.AA+rc.AA, lc.AA+rc.BA+1, lc.AB+rc.AA+1, lc.AB+rc.BA});
    ret.AB=min({lc.AA+rc.AB, lc.AA+rc.BB+1, lc.AB+rc.AB+1, lc.AB+rc.BB});
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

catdog.cpp: In member function 'void SEG::init(int, int, int)':
catdog.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In member function 'void SEG::update(int, int, int, int, Node)':
catdog.cpp:57:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In member function 'void SEG::query(int, int, int, int, int, std::vector<Node>&)':
catdog.cpp:67:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In member function 'Node SEG::query(int, int)':
catdog.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=1; i<V.size(); i++) ret=combine(ret, V[i]);
                  ~^~~~~~~~~
catdog.cpp:74:16: warning: unused variable 'j' [-Wunused-variable]
         int i, j;
                ^
catdog.cpp: In member function 'void SEG::debug(int, int, int)':
catdog.cpp:86:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:137:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
catdog.cpp: In function 'int query(int, int)':
catdog.cpp:174:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if(A[a]!=2) qa.AA-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1); C[a]-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
         ^~
catdog.cpp:174:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if(A[a]!=2) qa.AA-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1); C[a]-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
                                                                         ^
catdog.cpp:175:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if(A[a]!=1) qa.BB-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)); D[a]-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
         ^~
catdog.cpp:175:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if(A[a]!=1) qa.BB-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)); D[a]-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
                                                                         ^
catdog.cpp:178:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if(A[a]!=2) qa.AA+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1); C[a]+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
         ^~
catdog.cpp:178:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if(A[a]!=2) qa.AA+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1); C[a]+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
                                                                         ^
catdog.cpp:179:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if(A[a]!=1) qa.BB+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)); D[a]+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
         ^~
catdog.cpp:179:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if(A[a]!=1) qa.BB+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)); D[a]+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
                                                                         ^

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