QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378966 | #8575. Three Person Tree Game | ucup-team180# | AC ✓ | 99ms | 34568kb | C++23 | 7.6kb | 2024-04-06 15:30:18 | 2024-04-06 15:30:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
using ull = unsigned long long;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
template<class T> using pqmin = priority_queue<T, vector<T>, greater<T>>;
template<class T> using pqmax = priority_queue<T>;
const ll inf=LLONG_MAX/3;
const ll dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
const ll dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define si(x) ll(x.size())
#define rep(i,n) for(ll i=0;i<n;i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define rng(i,l,r) for(ll i=l;i<r;i++)
#define gnr(i,l,r) for(ll i=r-1;i>=l;i--)
#define fore(i, a) for(auto &&i : a)
#define fore2(a, b, v) for(auto &&[a, b] : v)
#define fore3(a, b, c, v) for(auto &&[a, b, c] : v)
template<class T> bool chmin(T& a, const T& b){ if(a <= b) return 0; a = b; return 1; }
template<class T> bool chmax(T& a, const T& b){ if(a >= b) return 0; a = b; return 1; }
template<class T, class U> bool chmin(T& a, const U& b){ return chmin(a, (T)b); }
template<class T, class U> bool chmax(T& a, const U& b){ return chmax(a, (T)b); }
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,...) vector<type>name(__VA_ARGS__)
#define VEC(type,name,size) vector<type>name(size);in(name)
#define VLL(name,size) vector<ll>name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>> name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,w) vector<vector<type>> name(h,vector<type>(w));in(name)
#define vvv(type,name,h,w,...) vector<vector<vector<type>>> name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
#define SUM(...) accumulate(all(__VA_ARGS__),0LL)
template<class T> auto min(const T& a){ return *min_element(all(a)); }
template<class T> auto max(const T& a){ return *max_element(all(a)); }
template<class T, class F = less<>> void sor(T& a, F b = F{}){ sort(all(a), b); }
template<class T> void uniq(T& a){ sor(a); a.erase(unique(all(a)), end(a)); }
void outb(bool x){cout<<(x?"Yes":"No")<<"\n";}
ll max(int x, ll y) { return max((ll)x, y); }
ll max(ll x, int y) { return max(x, (ll)y); }
int min(int x, ll y) { return min((ll)x, y); }
int min(ll x, int y) { return min(x, (ll)y); }
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define lbg(c, x) distance((c).begin(), lower_bound(all(c), (x), greater{}))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define ubg(c, x) distance((c).begin(), upper_bound(all(c), (x), greater{}))
ll gcd(ll a,ll b){return (b?gcd(b,a%b):a);}
vector<pll> factor(ull x){ vector<pll> ans; for(ull i = 2; i * i <= x; i++) if(x % i == 0){ ans.push_back({i, 1}); while((x /= i) % i == 0) ans.back().second++; } if(x != 1) ans.push_back({x, 1}); return ans; }
vector<ll> divisor(ull x){ vector<ll> ans; for(ull i = 1; i * i <= x; i++) if(x % i == 0) ans.push_back(i); per(i,ans.size() - (ans.back() * ans.back() == x)) ans.push_back(x / ans[i]); return ans; }
vll prime_table(ll n){vec(ll,isp,n+1,1);vll res;rng(i,2,n+1)if(isp[i]){res.pb(i);for(ll j=i*i;j<=n;j+=i)isp[j]=0;}return res;}
ll powmod(lll x,ll y,lll mod){lll res=1; while(y){ if(y&1)res=res*x%mod; x=x*x%mod; y>>=1;} return res; }
ll modinv(ll a,ll m){ll b=m,u=1,v=0;while(b){ll t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}u%=m;if(u<0)u+=m;return u;}
template <class T, class S> pair<T, S> operator-(const pair<T, S> &x) { return pair<T, S>(-x.first, -x.second); }
template <class T, class S> pair<T, S> operator-(const pair<T, S> &x, const pair<T, S> &y) { return pair<T, S>(x.fi - y.fi, x.se - y.se); }
template <class T, class S> pair<T, S> operator+(const pair<T, S> &x, const pair<T, S> &y) { return pair<T, S>(x.fi + y.fi, x.se + y.se); }
template <class T> pair<T, T> operator&(const pair<T, T> &l, const pair<T, T> &r) { return pair<T, T>(max(l.fi, r.fi), min(l.se, r.se)); }
template <class T, class S> pair<T, S> operator+=(pair<T, S> &l, const pair<T, S> &r) { return l = l + r; }
template <class T, class S> pair<T, S> operator-=(pair<T, S> &l, const pair<T, S> &r) { return l = l - r; }
template <class T> bool intersect(const pair<T, T> &l, const pair<T, T> &r) { return (l.se < r.se ? r.fi < l.se : l.fi < r.se); }
template <class T> vector<T> &operator++(vector<T> &v) {
fore(e, v) e++;
return v;
}
template <class T> vector<T> operator++(vector<T> &v, int) {
auto res = v;
fore(e, v) e++;
return res;
}
template <class T> vector<T> &operator--(vector<T> &v) {
fore(e, v) e--;
return v;
}
template <class T> vector<T> operator--(vector<T> &v, int) {
auto res = v;
fore(e, v) e--;
return res;
}
template <class T> vector<T> &operator+=(vector<T> &l, const vector<T> &r) {
fore(e, r) l.eb(e);
return l;
}
template<class... Ts> void in(Ts&... t);
[[maybe_unused]] void print(){}
template<class T, class... Ts> void print(const T& t, const Ts&... ts);
template<class... Ts> void out(const Ts&... ts){ print(ts...); cout << '\n'; }
namespace IO{
#define VOID(a) decltype(void(a))
struct S{ S(){ cin.tie(nullptr)->sync_with_stdio(0); fixed(cout).precision(12); } }S;
template<int I> struct P : P<I-1>{};
template<> struct P<0>{};
template<class T> void i(T& t){ i(t, P<3>{}); }
void i(vector<bool>::reference t, P<3>){ int a; i(a); t = a; }
template<class T> auto i(T& t, P<2>) -> VOID(cin >> t){ cin >> t; }
template<class T> auto i(T& t, P<1>) -> VOID(begin(t)){ for(auto&& x : t) i(x); }
template<class T, size_t... idx> void ituple(T& t, index_sequence<idx...>){ in(get<idx>(t)...); }
template<class T> auto i(T& t, P<0>) -> VOID(tuple_size<T>{}){ ituple(t, make_index_sequence<tuple_size<T>::value>{}); }
template<class T> void o(const T& t){ o(t, P<4>{}); }
template<size_t N> void o(const char (&t)[N], P<4>){ cout << t; }
template<class T, size_t N> void o(const T (&t)[N], P<3>){ o(t[0]); for(size_t i = 1; i < N; i++){ o(' '); o(t[i]); } }
template<class T> auto o(const T& t, P<2>) -> VOID(cout << t){ cout << t; }
template<class T> auto o(const T& t, P<1>) -> VOID(begin(t)){ bool first = 1; for(auto&& x : t) { if(first) first = 0; else o(' '); o(x); } }
template<class T, size_t... idx> void otuple(const T& t, index_sequence<idx...>){ print(get<idx>(t)...); }
template<class T> auto o(T& t, P<0>) -> VOID(tuple_size<T>{}){ otuple(t, make_index_sequence<tuple_size<T>::value>{}); }
#undef VOID
}
#define unpack(a) (void)initializer_list<int>{(a, 0)...}
template<class... Ts> void in(Ts&... t){ unpack(IO::i(t)); }
template<class T, class... Ts> void print(const T& t, const Ts&... ts){ IO::o(t); unpack(IO::o((cout << ' ', ts))); }
#undef unpack
void solve(){
string str="ABC";
LL(n);
VEC(ll,a,3);
a--;
vv(ll,g,n);
rep(i,n-1){
ll a,b;
cin>>a>>b;
a--,b--;
g[a].pb(b);
g[b].pb(a);
}
vec(ll,d,3,inf);
vv(ll,dist,3,n);
rep(j,3){
vll vis(n,0);
function<void(ll,ll)> dfs=[&](ll x,ll di){
dist[j][x]=di;
vis[x]=1;
fore(y,g[x]){
if(!vis[y]){
dfs(y,di+1);
}
}
};
dfs(a[j],0);
}
{
ll sum=inf;
rep(i,n){
ll s=0;
rep(j,3)s+=dist[j][i];
if(s<sum){
sum=s;
rep(j,3)d[j]=dist[j][i];
}
}
}
{
rep(j,3)if(d[j]==0){
if(j==2&&d[0]==1){
out("A");
return;
}
out(str[j]);
return;
}
}
rep(_,n+10){
rep(j,3){
if(d[j]==1&&d[(j+1)%3]==1);
else d[j]--;
if(d[j]==0){
out(str[j]);
return;
}
}
}
out("DRAW");
}
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
ll t;
cin>>t;
while(t--)solve();
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3592kb
input:
2 3 1 2 3 2 1 3 1 4 1 2 3 1 4 2 4 3 4
output:
A DRAW
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 25ms
memory: 3636kb
input:
10000 20 2 12 1 16 15 3 2 16 17 14 13 11 12 9 8 10 9 18 17 6 5 18 19 13 12 5 4 7 6 20 19 14 15 3 4 11 10 1 2 8 7 20 12 13 1 18 13 12 11 19 15 17 16 10 14 4 2 15 11 6 5 3 2 4 13 20 8 11 9 3 7 14 16 5 8 5 4 9 6 10 3 1 2 17 2 17 15 9 10 5 4 9 8 2 11 6 7 8 7 13 4 2 3 6 15 5 6 17 8 2 1 3 4 16 7 14 5 3 12...
output:
A B C B DRAW C A A A DRAW C B B B DRAW A DRAW A C DRAW A B A A A B B B C A A A B B DRAW C DRAW A A A A A B B A C DRAW A B A B DRAW A C DRAW A B C DRAW DRAW A A A DRAW DRAW B B B A DRAW B B A A DRAW B A A B DRAW A B A C DRAW A B A A A B B B A A B B A C DRAW B A B A A A C A A DRAW A A C A DRAW C A B A...
result:
ok 10000 lines
Test #3:
score: 0
Accepted
time: 39ms
memory: 4192kb
input:
100 2000 455 1301 981 1508 1509 1242 1243 1261 1260 190 191 1981 1980 591 592 1792 1791 1726 1727 959 960 134 135 1193 1192 836 835 1803 1804 1577 1578 1548 1549 718 717 1294 1295 1116 1117 59 58 138 139 425 426 1168 1169 1963 1962 1025 1026 867 866 892 893 589 588 871 872 891 892 722 721 1711 1712 ...
output:
C A A B DRAW C A B B DRAW B C B A DRAW B C A C DRAW C B A C DRAW A C C C DRAW B A A C DRAW C A B C DRAW B A B A DRAW A C B A DRAW B C C C DRAW A B B C DRAW C B C A DRAW A C B A DRAW B A B A DRAW C A C B DRAW A B C C DRAW C B C A DRAW B A C B DRAW A A A C DRAW
result:
ok 100 lines
Test #4:
score: 0
Accepted
time: 99ms
memory: 34568kb
input:
1 200000 123236 117321 150583 47722 47723 103604 103605 48192 48191 19204 19205 3666 3667 190708 190709 111542 111541 16125 16124 164298 164299 55406 55405 62042 62041 42100 42101 40664 40663 131742 131743 105518 105517 24249 24250 174387 174388 29840 29841 164536 164537 54802 54803 6378 6377 97486 ...
output:
A
result:
ok single line: 'A'
Test #5:
score: 0
Accepted
time: 94ms
memory: 22188kb
input:
1 200000 151854 28266 141391 178840 177656 70949 127572 92675 174074 38426 55569 16718 64264 72596 171817 36908 36081 44793 65081 114199 93358 10460 36725 18563 26764 77047 29901 17769 39712 109495 141203 24130 37855 165153 135141 94225 107789 57603 49313 197306 48518 61030 57058 199291 42676 60161 ...
output:
B
result:
ok single line: 'B'
Test #6:
score: 0
Accepted
time: 84ms
memory: 31220kb
input:
1 200000 107496 54564 62204 75611 75612 33562 133562 66786 66785 35079 35078 40044 40045 99675 199675 121963 21963 15671 15672 3062 103062 71627 171627 27125 127125 30049 30048 63164 63165 183373 83373 51319 51320 99879 199879 36383 136383 89110 89109 7607 107607 20098 20099 57792 157792 100415 415 ...
output:
B
result:
ok single line: 'B'
Test #7:
score: 0
Accepted
time: 88ms
memory: 21484kb
input:
1 200000 158505 85726 178357 30247 29809 107160 107392 84411 84297 80963 81018 64893 65118 194706 194894 8253 8478 47677 48197 120341 120487 68388 68653 41048 40580 128093 127913 118156 117983 97582 97422 166508 166267 171977 171895 108683 108912 102410 102283 130584 130479 75441 75592 145257 145092...
output:
A
result:
ok single line: 'A'
Test #8:
score: 0
Accepted
time: 13ms
memory: 3836kb
input:
10992 3 1 2 3 2 1 3 1 3 1 3 2 2 1 3 1 3 2 1 3 2 1 3 1 3 2 3 1 2 1 3 1 3 3 1 2 2 1 3 1 3 3 2 1 2 1 3 1 4 1 2 3 2 1 3 2 4 1 4 1 2 4 2 1 3 2 4 1 4 1 3 2 2 1 3 2 4 1 4 1 3 4 2 1 3 2 4 1 4 1 4 2 2 1 3 2 4 1 4 1 4 3 2 1 3 2 4 1 4 2 1 3 2 1 3 2 4 1 4 2 1 4 2 1 3 2 4 1 4 2 3 1 2 1 3 2 4 1 4 2 3 4 2 1 3 2 4 ...
output:
A A B A B A B A A A A A A B A A A A A B B B C A B B A B A C A A A A A A B B A DRAW A DRAW B B A DRAW A DRAW B B A DRAW A DRAW B A A A A A A A B A A A A B B A A A A A B A A C A B B B B B C A B C A C B B A A B A A C A A A A B B A C B A C C A B B B B A A A A A A A A A A A A B B A A A A A DRAW A A DRAW ...
result:
ok 10992 lines
Test #9:
score: 0
Accepted
time: 29ms
memory: 3836kb
input:
22222 9 1 2 3 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 4 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 5 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 6 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 7 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 8 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 2 9 2 1 3 2 4 3 5 4 6 1 7 6 8 7 9 8 9 1 3 2 2 1 3 ...
output:
B B B A A A A A B B A A A A A C B A A A A A C C A A A A A A A A B B B A A A A A B B A A A A A C B A A A A A C C A A A B B B B A B B A A A A A A B A A A A A A C A A A A A A A A B B B A A A A C B B A A A A C C B A A A A C C C A A A B B B B B A A B B B B A A B A A A A A A A A A A A C A A A B B B C A A ...
result:
ok 22222 lines
Extra Test:
score: 0
Extra Test Passed