QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#836924 | #5173. 染色 | lrx___ | 0 | 0ms | 0kb | C++20 | 9.5kb | 2024-12-29 10:25:13 | 2024-12-29 10:25:14 |
Judging History
answer
//#include <cctype>
//#include <climits>
//#include <cmath>
#include <cstdio>
//#include <cstdlib>
//#include <cstring>
//#include <ctime>
#include <algorithm>
//#include <array>
//#include <bitset>
//#include <deque>
//#include <functional>
//#include <list>
//#include <map>
#include <memory>
#include <numeric>
//#include <queue>
//#include <random>
#include <set>
//#include <sstream>
#include <string>
//#include <tuple>
//#include <utility>
#include <vector>
#define b_e(a) a.begin(),a.end()
#define F(i,a,b) for(i=a;i<=b;++i)
#define G(i,a,b) for(i=a;i>=b;--i)
#define R(i,a,b) for(i=a;i<b;++i)
#define P(i,a,b) for(i=a;i>b;--i)
typedef signed char i8;typedef unsigned char u8;
typedef short i16;typedef unsigned short u16;
typedef int i32;typedef unsigned u32;
typedef long long i64;typedef unsigned long long u64;
typedef float f32;typedef double f64;
namespace _ns{
template<typename T>T& max(T& a,T& b){return a>b?a:b;}
template<typename T,typename... A>T& max(T& a,T& b,A& ...c){return max(a=max(a,b),c...);}
template<typename T>T& min(T& a,T& b){return a<b?a:b;}
template<typename T,typename... A>T& min(T& a,T& b,A& ...c){return min(a=min(a,b),c...);}
const u32 buf_s(1<<21);bool ne;char i[buf_s],*ib(i),*ie(i),o[buf_s],*ob(o),a[20],&c(*a),*b;const char *oe(o+buf_s);
bool check(){return ~c&&c!=' '&&c!='\r'&&c!='\n';}
void n(){c=(ib==ie&&(ie=(ib=i)+fread(i,1,buf_s,stdin),ib==ie)?-1:*ib);}
void f(){ob-=fwrite(o,1,ob-o,stdout);}
void p(char c){if(ob==oe)f();*ob++=c;}
void r(i8& r){r=ne=false;for(n();c<'0'||c>'9';++ib,n())ne=(c=='-');for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');if(ne)r=~(r-1);}
void r(i16& r){r=ne=false;for(n();c<'0'||c>'9';++ib,n())ne=(c=='-');for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');if(ne)r=~(r-1);}
void r(int& r){r=ne=false;for(n();c<'0'||c>'9';++ib,n())ne=(c=='-');for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');if(ne)r=~(r-1);}
void r(i64& r){r=ne=false;for(n();c<'0'||c>'9';++ib,n())ne=(c=='-');for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');if(ne)r=~(r-1);}
void r(u8& r){r=0u;for(n();c<'0'||c>'9';++ib,n());for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');}
void r(u16& r){r=0u;for(n();c<'0'||c>'9';++ib,n());for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');}
void r(u32& r){r=0u;for(n();c<'0'||c>'9';++ib,n());for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');}
void r(u64& r){r=0u;for(n();c<'0'||c>'9';++ib,n());for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');}
void r(char* s){for(n();!check();++ib)n();for(*s++=c,n();check();++ib,n())*s++=c;*s=0;}
void r(std::string& s){s.clear();for(n();!check();++ib,n());for(s.push_back(c),++ib,n();check();++ib,n())s.push_back(c);}
void w(char r){p(r);}void w(char* s){for(;*s;p(*s++));}
void w(const char* s){for(;*s;p(*s++));}
void w(std::string s){w(s.data());}
void w(i8 r){if(r==0)return p('0');if(r<0)p('-'),r=~(r-1);for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
void w(i16 r){if(r==0)return p('0');if(r<0)p('-'),r=~(r-1);for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
void w(int r){if(r==0)return p('0');if(r<0)p('-'),r=~(r-1);for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
void w(i64 r){if(r==0)return p('0');if(r<0)p('-'),r=~(r-1);for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
void w(u8 r){if(r==0)return p('0');for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
void w(u16 r){if(r==0)return p('0');for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
void w(u32 r){if(r==0)return p('0');for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
void w(u64 r){if(r==0)return p('0');for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
template<typename T>void write(T& a){_ns::w(a);}
template<typename T,typename... A>void write(T& a,A&... b){write(a);write(b...);}
struct end_of_program{~end_of_program(){f();}}eop;
}
template<typename... A>void debug(A ...a){fprintf(stderr,a...);fflush(stderr);}
template<typename T,typename... A>T max(T a,A ...b){return _ns::max(a,b...);}
template<typename T,typename... A>T min(T a,A ...b){return _ns::min(a,b...);}
template<typename T1,typename T2>void to_max(T1& a,T2 b){if(a<b){a=b;}}
template<typename T1,typename T2>void to_min(T1& a,T2 b){if(b<a){a=b;}}
template<typename T>void read(T& a){_ns::r(a);}void read(char* s){_ns::r(s);}
template<typename T,typename... A>void read(T& a,A&... b){read(a);read(b...);}
template<typename... A>void write(A... a){_ns::write(a...);}
template<typename... ex>class graph{
private:
struct edge{
int v;
std::tuple<ex...> w;
edge *p;
template<int k>auto& get()const{return std::get<k>(w);}
edge*& next(){return p;}
}**h,*e,*p;
void __init__(){
if(h){
delete[] h;
delete[] e;
h=nullptr;e=nullptr;
}
}
public:
typedef edge* iterator;
graph():h(nullptr),e(nullptr),p(nullptr){}
~graph(){__init__();}
void init(int n,int m){
__init__();
h=new edge*[n+1];
std::fill(h,h+n+1,nullptr);
e=new edge[m];
p=e;
}
void add(int u,int v,ex... a){
p->p=h[u];
p->v=v;
p->w=std::make_tuple(a...);
h[u]=p++;
}
edge*& head(int u){
return h[u];
}
};
template<typename T>class graph<T>{
private:
struct edge{
int v;
T w;
edge *p;
T& get()const{return w;}
edge*& next(){return p;}
}**h,*e,*p;
void __init__(){
if(h){
delete[] h;
delete[] e;
h=nullptr;e=nullptr;
}
}
public:
typedef edge* iterator;
graph():h(nullptr),e(nullptr),p(nullptr){}
~graph(){__init__();}
void init(int n,int m){
__init__();
h=new edge*[n+1];
std::fill(h,h+n+1,nullptr);
e=new edge[m];
p=e;
}
void add(int u,int v,T w){
p->p=h[u];
p->v=v;
p->w=w;
h[u]=p++;
}
edge*& head(int u){
return h[u];
}
};
template<>class graph<>{
private:
struct edge{
int v;
edge *p;
edge*& next(){return p;}
}**h,*e,*p;
void __init__(){
if(h){
delete[] h;
delete[] e;
h=nullptr;e=nullptr;
}
}
public:
typedef edge* iterator;
graph():h(nullptr),e(nullptr),p(nullptr){}
~graph(){__init__();}
void init(int n,int m){
__init__();
h=new edge*[n+1];
std::fill(h,h+n+1,nullptr);
e=new edge[m];
p=e;
}
void add(int u,int v){
p->p=h[u];
p->v=v;
h[u]=p++;
}
edge*& head(int u){return h[u];}
};
constexpr int A(1e6+5);
int fa[A],sz[A],num[A],dfn,rk[A],beg[A],que[A],n,m;
std::set<int> se;
graph<> g;
void dfs(int u,int father){
int v;
graph<>::iterator e;
fa[u]=father;
sz[u]=1;
num[u]=++dfn;
rk[dfn]=u;
for(e=g.head(u);e;e=e->next()){
v=e->v;
if(v!=father){
dfs(v,u);
sz[u]+=sz[v];
}
}
}
#define ls u<<1
#define rs u<<1|1
namespace t1{
int col[A<<2];
void build(int u=1,int l=1,int r=n){
if(l==r){
col[u]=1;
return;
}
col[u]=-1;
const int mid((l+r)>>1);
build(ls,l,mid);
build(rs,mid+1,r);
}
#define tag(u,k) col[u]=k
void push_down(int u){
if(~col[u]){
tag(ls,col[u]);
tag(rs,col[u]);
col[u]=-1;
}
}
void update(int x,int y,int k,int u=1,int l=1,int r=n){
if(x<=l&&r<=y){
tag(u,k);
return;
}
push_down(u);
const int mid((l+r)>>1);
if(x<=mid){
update(x,y,k,ls,l,mid);
}
if(mid<y){
update(x,y,k,rs,mid+1,r);
}
}
int query(int x){
int u(1),l(1),r(n),mid;
for(;l<r;){
push_down(u);
mid=(l+r)>>1;
if(x<=mid){
u=ls;r=mid;
}else{
u=rs;l=mid+1;
}
}
return col[u];
}
#undef tag
}
namespace dsu{
int f[A],s[A],sta[A][2],top;
void init(){
std::iota(f+1,f+n+1,1);
std::fill(s+1,s+n+1,1);
}
int fd(int k){
return f[k]==k?k:fd(f[k]);
}
void merge(int u,int v){
u=fd(u);v=fd(v);
if(u!=v){
if(s[u]>s[v]){
std::swap(u,v);
}
sta[++top][0]=u;
sta[top][1]=v;
f[u]=v;s[v]+=s[u];
}
}
void back(){
int u,v;
u=sta[top][0];
v=sta[top--][1];
f[u]=u;
s[v]-=s[u];
}
}
namespace t2{
std::vector<int> t[A<<2];
void add(int k,int x,int y,int u=1,int l=1,int r=m){
// if(u==1){
// debug("k=%d x=%d y=%d\n",k,x,y);
// }
if(x<=l&&r<=y){
t[u].push_back(k);
return;
}
const int mid((l+r)>>1);
if(x<=mid){
add(k,x,y,ls,l,mid);
}
if(mid<y){
add(k,x,y,rs,mid+1,r);
}
}
void solve(int u=1,int l=1,int r=m){
for(auto& i:t[u]){
dsu::merge(i,fa[i]);
}
if(l==r){
if(que[l]){
write(dsu::s[dsu::fd(que[l])],'\n');
}
}else{
const int mid((l+r)>>1);
solve(ls,l,mid);
solve(rs,mid+1,r);
}
int len(t[u].size());
for(;len--;){
dsu::back();
}
}
}
#undef ls
#undef rs
int main(){
int i,o,u,v;
std::set<int>::iterator it;
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
read(n);
g.init(n,(n-1)<<1);
F(i,2,n){
read(u,v);
g.add(u,v);
g.add(v,u);
}
dfs(1,0);
t1::build();
std::fill(beg+1,beg+n+1,1);
read(m);
F(i,1,m){
read(o,u);
if(o==1){
read(v);
t1::update(num[u],num[u]+sz[u]-1,v);
if(se.size()){
for(it=se.lower_bound(num[u]+1);it!=se.end()&&*it<num[u]+sz[u];it=se.erase(it)){
beg[rk[*it]]=i;
}
}
if(u>1){
if(t1::query(num[u])==t1::query(num[fa[u]])){
if(se.count(num[u])){
beg[u]=i;
se.erase(num[u]);
}
}else{
if(!se.count(num[u])){
if(i>1){
t2::add(u,beg[u],i-1);
}
se.insert(num[u]);
}
}
}
}else{
que[i]=u;
}
}
F(i,2,n){
if(!se.count(num[i])){
t2::add(i,beg[i],m);
}
}
dsu::init();
t2::solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
input:
10000 100 84 85 52 2 78 53 20 21 23 76 37 44 18 5 37 8 81 65 46 58 69 1 69 37 53 46 37 35 35 89 1 77 35 6 46 59 89 46 25 55 50 38 61 67 44 23 29 24 46 4 42 15 34 77 20 34 83 79 12 50 69 26 38 14 9 66 80 72 22 26 9 68 35 38 19 84 92 30 83 62 100 71 81 60 7 37 64 50 33 60 86 75 45 78 32 53 3 48 87 60 ...
output:
result:
Subtask #2:
score: 0
Dangerous Syscalls
Test #7:
score: 0
Dangerous Syscalls
input:
100000 100000 3 2 3 3 3 3 2 3 2 1 3 1 1 1 3 2 1 3 1 2 2 1 3 1 2 2 1 1 1 3 2 1 3 3 3 3 1 1 1 2 3 3 2 1 1 1 3 1 3 1 3 2 1 3 2 3 3 2 3 3 2 3 3 3 3 3 2 3 2 3 1 3 3 3 3 3 3 3 1 2 3 3 1 3 1 1 2 2 3 1 1 2 3 2 3 1 3 2 1 3 2 3 2 1 1 3 3 1 3 1 2 2 2 3 2 3 2 3 2 1 1 3 1 3 2 2 3 3 3 1 2 2 3 3 2 1 3 1 2 2 2 3 2 ...
output:
result:
Subtask #3:
score: 0
Dangerous Syscalls
Test #15:
score: 0
Dangerous Syscalls
input:
5000 5000 256 63 197 36 75 66 33 72 27 75 66 248 29 166 209 252 141 95 84 226 147 249 116 94 192 256 199 273 182 166 116 274 27 211 154 144 283 23 53 110 215 11 164 284 161 221 251 96 43 47 18 115 12 51 156 61 116 209 93 98 47 165 174 106 83 67 184 75 12 290 183 197 112 240 67 56 215 148 104 5 141 2...
output:
result:
Subtask #4:
score: 0
Dangerous Syscalls
Test #23:
score: 0
Dangerous Syscalls
input:
1000000 1000000 1105 3246 1880 3554 818 2331 2576 4140 149 4562 3498 3536 3400 4788 4363 4742 1216 4218 4032 1701 1489 4889 1761 3022 3145 4945 3067 4304 5016 4624 1612 13 1335 3613 1086 2210 386 3464 1156 3352 4341 5006 3465 3900 622 654 1826 2983 1250 4164 3335 4308 2995 1982 1347 4335 2535 5054 4...