| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 421329 |
2021-06-09T04:00:25 Z |
송준혁(#7507) |
Cats or Dogs (JOI18_catdog) |
C++17 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define INF (1ll<<62)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N, Q;
int A[101010], C[101010], D[101010];
vector<int> adj[101010];
int I[101010], Pa[101010], num;
int L[101010], R[101010];
int P[101010], W[101010];
struct Node{
int cc, cd, dc, dd;
Node(){cc=dd=0, cd=dc=1;}
void trm(){
cc = min(cc, cd+1), cc = min(cc, dc+1), cc = min(cc, dd+2);
cd = min(cd, cc+1), cd = min(cd, dd+1), cd = min(cd, dc+2);
dc = min(dc, cc+1), dc = min(dc, dd+1), dc = min(dc, cd+2);
dd = min(dd, cd+1), dd = min(dd, dc+1), dd = min(dd, cc+2);
}
Node operator+(const Node &r)const{
Node ret;
ret.cc = min(cc+r.cc, cd+r.dc);
ret.cd = min(cc+r.cd, cd+r.dd);
ret.dc = min(dc+r.cc, dd+r.dc);
ret.dd = min(dc+r.cd, dd+r.dd);
ret.trm();
return ret;
}
} T[404040];
void dfs(int u, int p){
W[u] = 1, Pa[u] = p;
for (int v : adj[u]){
if (v == p) continue;
dfs(v, u), W[u]+=W[v];
}
sort(adj[u].begin(), adj[u].end(), [&](int a, int b){
if (a == p) return false;
if (b == p) return true;
return W[a] > W[b];
});
if (u>1) adj[u].pop_back();
}
void hld(int u, int r){
I[u] = ++num, L[I[u]] = I[r], R[I[r]] = I[u];
if (!adj[u].size()) return;
hld(adj[u][0], r);
for (int i=1; i<adj[u].size(); i++) hld(adj[u][i], adj[u][i]);
}
void upd(int id, int s, int e, int t){
if (e < t || t < s) return;
if (s == e){
T[id].cc=T[id].cd=T[id].dc=T[id].dd=N;
if (A[t] != 1) T[id].dd=D[t];
if (A[t] != 2) T[id].cc=C[t];
T[id].trm();
return;
}
int m=s+e>>1;
upd(id*2, s, m, t), upd(id*2+1, m+1, e, t);
T[id] = T[id*2] + T[id*2+1];
}
Node sum(int id, int s, int e, int ts, int te){
if (e < ts || te < s) return Node();
if (ts <= s && e <= te) return T[id];
int m=s+e>>1;
return sum(id*2, s, m, ts, te)+sum(id*2+1, m+1, e, ts, te);
}
int main(){
Node t;
scanf("%d", &N);
for (int i=1; i<N; i++){
int u, v;
scanf("%d %d", &u, &v);
adj[u].pb(v), adj[v].pb(u);
}
dfs(1, 0), hld(1, 1);
for (int i=1; i<=N; i++) P[I[i]] = I[Pa[i]];
scanf("%d", &Q);
while (Q--){
int u, x;
scanf("%d %d", &x, &u);
u = I[u], A[u] = x;
while (u){
t = sum(1, 1, N, L[u], R[L[u]]);
C[P[L[u]]] -= min(t.cc, t.cd);
D[P[L[u]]] -= min(t.dc, t.dd);
upd(1, 1, N, u);
t = sum(1, 1, N, L[u], R[L[u]]);
C[P[L[u]]] += min(t.cc, t.cd);
D[P[L[u]]] += min(t.dc, t.dd);
u = P[L[u]];
}
printf("%d\n", min(C[0], D[0]));
}
return 0;
}
Compilation message
catdog.cpp: In function 'void hld(int, int)':
catdog.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i=1; i<adj[u].size(); i++) hld(adj[u][i], adj[u][i]);
| ~^~~~~~~~~~~~~~
catdog.cpp: In function 'void upd(int, int, int, int)':
catdog.cpp:69:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int m=s+e>>1;
| ~^~
catdog.cpp: In function 'Node sum(int, int, int, int, int)':
catdog.cpp:77:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | int m=s+e>>1;
| ~^~
catdog.cpp: In function 'int main()':
catdog.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
catdog.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
catdog.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
catdog.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d %d", &x, &u);
| ~~~~~^~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccEjUbG8.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccDKx5M9.o:catdog.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccEjUbG8.o: in function `main':
grader.cpp:(.text.startup+0x1e2): undefined reference to `initialize(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: grader.cpp:(.text.startup+0x219): undefined reference to `neighbor(int)'
/usr/bin/ld: grader.cpp:(.text.startup+0x25e): undefined reference to `dog(int)'
/usr/bin/ld: grader.cpp:(.text.startup+0x269): undefined reference to `cat(int)'
collect2: error: ld returned 1 exit status
