QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #331392 | #8055. Balance | ucup-team008 | RE | 2ms | 8056kb | C++23 | 17.1kb | 2024-02-18 07:23:37 | 2024-02-18 07:23:37 |
Judging History
answer
// {{{ y0105w49 template 22M14
// hi mom
#ifndef NULL
#ifdef __GNUC__
#ifndef __clang__
// #include <bits/stdc++.h>
#include <bits/extc++.h>
#include <tr2/dynamic_bitset>
#define EXTS
#else
#ifdef ARST
#include <bits/clang++.h>
#else
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
// #include <cuchar>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#if __cplusplus >= 201402L
#include <shared_mutex>
#endif
#if __cplusplus >= 201703L
#include <any>
#include <charconv>
// #include <execution>
#include <filesystem>
#include <optional>
// #include <memory_resource>
#include <string_view>
#include <variant>
#endif
#if __cplusplus >= 202002L
#include <barrier>
#include <bit>
#include <compare>
#include <concepts>
#if __cpp_impl_coroutine
# include <coroutine>
#endif
#include <latch>
#include <numbers>
#include <ranges>
#include <span>
// #include <stop_token>
#include <semaphore>
// #include <source_location>
// #include <syncstream>
#include <version>
#endif
#if __cplusplus > 202002L
// #include <expected>
// #include <spanstream>
#if __has_include(<stacktrace>)
# include <stacktrace>
#endif
#include <stdatomic.h>
#endif
#endif
#endif
#else
#error "unsupported"
#endif
#endif
using namespace std;
#ifdef ARST
#define JO 1
#define OJ 0
#else
#define JO 0
#define OJ 1
#endif
#define STR(x) #x
#define GCCDIAG(s) _Pragma(STR(GCC diagnostic s)) static_assert(true)
#define Wsave GCCDIAG(push)
#define Wpop GCCDIAG(pop)
#define Wsupp(w) GCCDIAG(ignored "-W" w)
#define Wpush(w) Wsave; Wsupp(w)
#define typeof __typeof__
namespace gbd_ns {
template<typename C>
struct is_iterable {
template<class T> static long check(...);
template<class T> static char check(int,typename T::const_iterator = C().end());
enum {
value = sizeof(check<C>(0)) == sizeof(char),
neg_value = sizeof(check<C>(0)) != sizeof(char)
};
};
template<class T> struct _gbd3C;
template<class T> ostream &_gbd3(ostream &os,const T &x) { return _gbd3C<T>::call(os,x); }
template<> ostream &_gbd3(ostream &os,const string &x) { return os<<'"'<<x<<'"'; }
template<> ostream &_gbd3(ostream &os,char *const &x) { return os<<'"'<<x<<'"'; }
template<class T> ostream &_gbd3_5(ostream &os,const T &x) { return _gbd3(os,x); }
template<class A,class B>
ostream &_gbd4(ostream &os,const pair<A,B> &p) {
_gbd3(os<<'(',p.first);
_gbd3(os<<',',p.second);
return os<<')';
}
template<class T,size_t N> struct _gbd4_tupleC {
static void call(ostream &os,const T &t) {
_gbd4_tupleC<T,N-1>::call(os,t);
os<<','<<get<N-1>(t);
}
};
template<class T> struct _gbd4_tupleC<T,1> {
static void call(ostream &os,const T &t) {
os<<get<0>(t);
}
};
template<typename... Types>
ostream &_gbd4(ostream &os,const tuple<Types...> &t) {
os<<'(';
_gbd4_tupleC<tuple<Types...>,sizeof...(Types)>::call(os,t);
return os<<')';
}
template<>
ostream &_gbd4(ostream &os,const tuple<> &t) { (void)t; return os<<"()"; }
template<class T> ostream &_gbd4(ostream &os,const T &x) {
return os<<x;
}
template<class T> struct _gbd3C {
template<class U=T>
static ostream &call(ostream &os,enable_if_t<is_iterable<U>::value,const T> &V) {
os<<"{";
bool ff=0;
for(const auto &E:V) _gbd3_5<decltype(E)>(ff?os<<",":os,E), ff=1;
return os<<"}";
}
template<class U=T>
static ostream &call(ostream &os,enable_if_t<is_iterable<U>::neg_value,const T> &x) {
return _gbd4(os,x);
}
};
template<class T,typename... Args> ostream &_gbd2(ostream &os,bool,vector<string>::iterator nm,const T &x,Args&&... args);
ostream &_gbd2(ostream &os,bool,vector<string>::iterator) { return os; }
template<typename... Args>
ostream &_gbd2(ostream &os,bool fi,vector<string>::iterator nm,const char *x,Args&&... args) {
return _gbd2(os<<(fi?"":" ")<<x,0,nm+1,args...);
}
template<class T,typename... Args>
ostream &_gbd2(ostream &os,bool fi,vector<string>::iterator nm,const T &x,Args&&... args) {
return _gbd2(_gbd3<T>(os<<(fi?"":" ")<<*nm<<"=",x),0,nm+1,args...);
}
vector<string> split(string s) {
vector<string> Z;
string z="";
s+=',';
int dep=0;
for(char c:s) {
if(c==',' && !dep) Z.push_back(z),z="";
else z+=c;
if(c=='(' || c=='{' || c=='[') ++dep;
if(c==')' || c=='}' || c==']') --dep;
}
return Z;
}
template<typename... Args> ostream &_gbd1(ostream &os,const string &nm,Args&&... args) {
return _gbd2(os,1,split(nm).begin(),args...);
}
template<typename... Args> string _gbd1(const string &nm,Args&&... args) {
ostringstream oss;
_gbd2(oss,1,split(nm).begin(),args...);
return oss.str();
}
}
bool DBG=1,EMACS=0;
#define dbg(...) (JO&&DBG?gbd_ns::_gbd1(cerr<<"\033[38;5;5m"<<__FILE__<<":"<<__LINE__<<(EMACS?":note: ":": "),#__VA_ARGS__,__VA_ARGS__)<<"\033[0m"<<endl:cerr)
#define dbgt(...) dbg(fmt_time(),__VA_ARGS__)
#define fmt(...) gbd_ns::_gbd1(#__VA_ARGS__,__VA_ARGS__)
template<class Fun> struct _y_combinator_result {
Fun _fun;
template<class T> explicit _y_combinator_result(T &&fun) : _fun(forward<T>(fun)) {}
template<typename... Args> decltype(auto) operator()(Args &&... args) {
return _fun(ref(*this),forward<Args>(args)...);
}
};
template<class Fun> [[nodiscard]] decltype(auto) fix(Fun &&fun) {
return _y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
}
#define nop void()
#define sz(x) (int((x).size()))
#define all(v) (v).begin(),(v).end()
#define sortu(v) (sort(all(v)), (v).resize(unique(all(v))-begin(v)))
#define forenum(i,...) for(int i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else
#define forenumll(i,...) for(long long i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else
#define forbs(k,i,bs) for(ptrdiff_t k=0,i=(bs)._Find_first();i<(ptrdiff_t)(bs).size();i=(bs)._Find_next(i),++k)
#define fordbs(k,i,bs) for(ptrdiff_t k=0,i=(bs).find_first();i<(ptrdiff_t)(bs).size();i=(bs).find_next(i),++k)
#define get(x,i) get<i>(x)
template<class T> bool inb(const T &x,const T &l,const T &r) { return l<=x&&x<=r; }
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#ifdef EXTS
template<class S,class T> using omap=__gnu_pbds::tree<S,T,less<S>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<class T> using oset=omap<T,__gnu_pbds::null_type>;
template<class T> using rope=__gnu_cxx::rope<T>;
using dbitset=tr2::dynamic_bitset<>;
#endif
constexpr int e0=1, e1=10, e2=100, e3=1000;
constexpr int e4=10*e3, e5=100*e3, e6=1000*e3;
constexpr int e7=10*e6, e8=100*e6, e9=1000*e6;
constexpr long long e10=10LL*e9, e11=100LL*e9, e12=1000LL*e9;
constexpr long long e13=10*e12, e14=100*e12, e15=1000*e12;
constexpr long long e16=10*e15, e17=100*e15, e18=1000*e15;
constexpr __int128_t e21=__int128_t(e3)*e18, e24=__int128_t(e6)*e18, e27=__int128_t(e9)*e18;
constexpr __int128_t e30=e3*e27, e33=e6*e27, e36=e9*e27;
using ulll=__uint128_t;
using lll=__int128_t;
using ull=unsigned long long;
using ll=long long;
using ld=long double;
#ifdef EXTS
using lld=__float128;
#endif
long long START_TIME=chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now().time_since_epoch()).count();
inline long long now_U_03BC_s() { return chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now().time_since_epoch()).count()-START_TIME; }
const char *fmt_time(long long U_03BC_s=now_U_03BC_s()) { static char dur[20]; sprintf(dur,"%llu.%03llus",U_03BC_s/e6,(U_03BC_s%e6)/e3); return dur; }
#define timed(cb) do { dbg("timed "#cb" ..."); unsigned long long start=now_U_03BC_s(); cb; dbg("timed "#cb" took",fmt_time(now_U_03BC_s()-start)); } while(0)
int arg1; bool inp; vector<string> args;
unsigned seed=unsigned(JO&&getenv("sd")?atoi(getenv("sd")):OJ?START_TIME:START_TIME%e5);
mt19937 igen(seed<<1),gen(seed<<1|1);
#define irand(...) _rand(igen,__VA_ARGS__)
#define rand(...) _rand(gen,__VA_ARGS__)
template<class T> enable_if_t<numeric_limits<T>::is_integer,T> _rand(mt19937 &g,T l,T r) { return uniform_int_distribution<T>(l,r)(g); }
template<class T> enable_if_t<numeric_limits<T>::is_integer,T> _rand(mt19937 &g,T n) { return _rand(g,T(1),n); }
[[deprecated]] int _rand(mt19937 &g) { return _rand(g,0,numeric_limits<int>::max()); }
template<class T> enable_if_t<numeric_limits<T>::is_iec559,T> _rand(mt19937 &g,T l,T r) { return uniform_real_distribution<T>(l,r)(g); }
bool _rand(mt19937 &g,double p) { return bernoulli_distribution(p)(g); }
template<class T> T _rand(mt19937 &g,initializer_list<T> il) { return *(il.begin()+_rand(g,0,(int)il.size()-1)); }
template<class T> T _rand(mt19937 &g,double p,T a,T b) { return _rand(g,p)?a:b; }
template<class T> T _rand(mt19937 &g,initializer_list<T> il,initializer_list<double> wt) { assert(il.size()==wt.size()); return *(il.begin()+discrete_distribution<int>(wt)(g)); }
#define random_shuffle(...) static_assert(false,"random_shuffle deprecated, use shuffle")
#define ine(x,e) (inp?cin>>(x),nop:((x)=(e),nop))
#define inr(x,...) ine(x,irand(__VA_ARGS__))
#define endl '\n'
string garb;
void exit0() { DBG=1; dbgt("gg (early)"); exit(0); }
#ifndef MAIN
#define MAIN _main
#endif
void MAIN();
int32_t main([[maybe_unused]]int argc,[[maybe_unused]]char *argv[]) {
ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(ios_base::failbit | ios_base::badbit);
arg1=0,args={argv,argv+argc};
if(sz(args)>1) {
if(args[1][0]=='i') freopen((string(__FILE__).substr(0,string(__FILE__).find('.'))+"."+args[1].substr(1)+".in").c_str(),"r",stdin);
else if(args[1][0]=='I') freopen(args[1].substr(1).c_str(),"r",stdin);
else arg1=stoi(args[1]);
}
inp=!arg1;
if(JO && getenv("EMACS")) EMACS=1;
dbgt(arg1,seed,args);
#ifdef QUIET
DBG=0;
#endif
MAIN();
DBG=1;
dbgt("gg;wp");
return 0;
}
constexpr int inf=e9+99;
constexpr ll linf=1LL*e9*e9+99;
#if __cplusplus >= 202002L
constexpr long double U_03C4__ld=2*numbers::pi_v<long double>;
#else
const long double U_03C4__ld=2*acosl(-1);
#endif
#define U_03C4_ ((flt)U_03C4__ld)
constexpr long double U_03B5__ld=1e-8l;
#define U_03B5_ ((flt)U_03B5__ld)
// }}}
using flt=double; //CARE
constexpr int P=e9+7;//998'244'353;
// Biconnected components in a graph.
// Input:
// - Undirected, not necessarily connected, graph.
// - Populate e[] array with pairs of
// opposite edges (a->b) and (b->a)
// Call:
// - bicon(N,M) where:
// - N is the number of vertices (0-indexed)
// - M is the number of edges
// This should be HALF the number of entries in e[]
// Returns:
// - Bridges (edges whose removal disconnects verts)
// - Articulation Vertices (vertices, ditto)
// - Biconnected components (blocks) defined
// by articulation vertices.
// - If you want biconnected components defined by
// the bridges, do it yourself (delete all the
// bridges, and the remaining components are
// what you are looking for)
#define CLR(s) memset((s),0,sizeof(int)*n+77)
#define CLR2(s) memset((s),0,sizeof(int)*m*2+77)
// #define CLR(s) memset((s),0,sizeof((s)))
// #define CLR2(s) memset((s),0,sizeof((s)))
#define stack arsent
#define MAXE (400<<10) // twice the max # edges
#define MAXV (100<<10) // max # vertices
struct ee { int from, to; } e[MAXE];
int firste[MAXV];
int pre[MAXV], //preorder visit order
lowp[MAXV], //lowest pre for cycle
stack[MAXV], sp; //component stack
vector<int> artic; // articulation verts
vector<pair<int,int> > bridge; // bridge
vector<set<int> > vcomp; // edge-biconnected comps
int bicon_dfs(int me, int pp, int p) {
int i,v, bdgs=0, comps=0;
if (!p) sp = -1;
stack[++sp] = me;
pre[me] = lowp[me] = p++;
for (i=firste[me];e[i].from==me;i++) {
v = e[i].to;
if (!pre[v]) {
p = bicon_dfs(v, pre[me], p);
lowp[me] = min(lowp[me], lowp[v]);
if (lowp[v] == pre[me]) {
set<int> foo;
foo.insert(me); foo.insert(v);
for(; stack[sp]-v; sp--)
foo.insert(stack[sp]);
sp--;
vcomp.push_back(foo);
comps++;
} else if (lowp[v] == pre[v]) {
bridge.push_back({me,v});
sp--;
bdgs++;
}
}
else if (pre[v] < pp)
lowp[me] = min(lowp[me], pre[v]);
}
if (bdgs + comps + !!pp >= 2)
artic.push_back(me);
if (lowp[me] == pre[me] && !comps) {
set<int> foo;
foo.insert(me);
vcomp.push_back(foo);
}
return p;
}
bool comp(const ee&a, const ee&b){
if (a.from==b.from) return a.to<b.to;
return a.from < b.from;
}
void clear(int n,int m) { // if you need it
artic.clear(); bridge.clear(); vcomp.clear();
CLR2(e); CLR(pre); CLR(lowp); CLR(stack); CLR(firste);
sp = -1;
}
void bicon(int N, int M) {
int n=N;
CLR(firste); sort(e,e+2*M,comp);
e[2*M].from = e[2*M].to = -1;
for(int i=0;i<2*M;++i)
if (i == 0 || e[i].from != e[i-1].from)
firste[e[i].from] = i;
for(int i=0;i<N;++i) if (!pre[i]) bicon_dfs(i,0,1);
}
void _m() {
int n,m; ine(n,arg1), inr(m,n-1,arg1*2);
clear(n,m);
map<pair<int,int>,int> es;
for(int i=1;i<=m;i++) {
int u,v;
if(i<n) inr(u,i), ine(v,i+1);
else inr(u,n), inr(v,n);
e[i*2-2]={u,v};
e[i*2-1]={v,u};
++es[minmax(u,v)];
}
bicon(n,m);
const int N=100<<10;
set<pair<int,int>> bridges(all(bridge));
static int da[N]; for(int i=1;i<=n;i++) da[i]=0;
auto rt=fix([&](auto rec,int u) -> int { return da[u]?da[u]=rec(da[u]):u; });
for(int i=1;i<=m;i++) {
auto [u,v]=e[i*2-2];
if(es[minmax(u,v)]==1) {
if(bridges.count({u,v})) continue;
if(bridges.count({v,u})) continue;
}
u=rt(u),v=rt(v);
if(u==v) continue;
da[u]=v;
}
static vector<int> adj[N]; for(int i=1;i<=n;i++) adj[i].clear();
for(auto [u,v]:bridges) {
if(es[minmax(u,v)]>=2) continue;
u=rt(u),v=rt(v);
assert(u!=v);
adj[u].pb(v);
adj[v].pb(u);
}
static int wt[N];
for(int u=1;u<=n;u++) wt[u]=0;
for(int u=1;u<=n;u++) ++wt[rt(u)];
static int siz[N],pa[N];
// for(int u=1;u<=n;u++) if(u==rt(u)) dbg(u,adj[u]);
// dbg(n,m,bridge);
assert(fix([&](auto rec,int u,int p=-1) -> int {
pa[u]=p;
siz[u]=wt[u];
for(int v:adj[u]) if(v!=p) siz[u]+=rec(v,u);
return siz[u];
})(rt(1))==n);
auto SIZ=[&](int u,int p) -> int {
// dbg(u,p,siz[u],pa[u]);
if(!~p) return n;
if(pa[u]==p) return siz[u];
assert(pa[p]==u);
return n-siz[p];
};
static int a[N];
for(int i=1;i<=n;i++) inr(a[i],n);
sort(a+1,a+1+n);
static int mn[N];
for(int i=1;i<=n;i++) mn[i]=inf;
for(int i=n;i>=1;i--) mn[a[i]]=i;
static vector<pair<int,int>> todos[N]; for(int u=1;u<=n;u++) todos[u].clear();
for(int u=1;u<=n;u++) for(int v:adj[u]) todos[u].pb({SIZ(v,u),v});
for(int u=1;u<=n;u++) sort(all(todos[u]));
static int COL[N]; for(int u=1;u<=n;u++) COL[u]=-1;
auto colourize=fix([&](auto rec,int u,int p,int c) -> void {
assert(!~COL[u]); COL[u]=c;
for(int v:adj[u]) if(v!=p) rec(v,u,c);
});
auto f=fix([&](auto rec,int u,int p=-1) -> bool {
#define todos todos[u]
int hi=SIZ(u,p);
int lo=mn[a[hi]];
assert(a[lo]==a[hi]);
assert(a[lo-1]!=a[hi]);
if(lo==1) dbg(u,p,lo,hi,a[lo],a[hi]);
if(lo==1) return colourize(u,p,a[hi]),1;
bool PB=0;
for(;sz(todos) && todos.back().fi>=lo-1;) {
int v=todos.back().se; todos.pop_back();
if(v==p) { assert(!PB); PB=1; continue; }
if(!rec(v,u)) continue;
for(int w:adj[u]) if(w!=v && w!=p) colourize(w,u,a[hi]);
assert(!~COL[u]); COL[u]=a[hi];
return 1;
}
if(PB) todos.pb({SIZ(p,u),p});
#undef todos
return 0;
});
for(int u=1;u<=n;u++) if(rt(u)==u && f(u)) goto win;
cout<<"No"<<endl;
return;
win:;
cout<<"Yes"<<endl;
for(int u=1;u<=n;u++) cout<<COL[rt(u)]<<" \n"[u==n];
}
void _main() { /* CURSOR START */
int T; ine(T,5); for(;T--;) _m();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8056kb
input:
5 5 4 1 2 2 3 3 4 4 5 1 2 3 4 5 5 4 1 2 1 3 1 4 1 5 1 2 3 4 5 5 4 1 2 1 3 1 4 1 5 1 2 2 2 3 5 6 1 2 1 2 2 3 3 4 4 5 3 5 1 2 1 2 1 2 2 1 2 1 2 1 2
output:
Yes 5 4 3 2 1 No Yes 2 3 2 2 1 Yes 2 2 1 1 1 No
result:
ok ok (5 test cases)
Test #2:
score: -100
Runtime Error
input:
100000 4 3 4 2 1 3 2 1 2 1 3 2 5 7 2 5 5 3 2 3 5 1 4 3 2 4 4 3 1 3 1 1 2 3 2 2 1 2 3 1 1 1 4 7 3 4 1 4 2 3 4 3 4 2 3 1 4 3 2 3 3 2 4 6 2 4 3 1 1 2 1 2 2 3 4 2 1 1 3 3 4 7 3 2 4 2 1 2 3 4 3 2 2 4 3 4 2 1 1 1 5 5 3 2 1 5 4 5 4 3 2 1 1 2 2 3 2 3 5 2 3 1 3 3 1 3 1 2 1 3 2 3 2 3 2 1 2 1 1 2 1 1 2 3 2 1 1...