QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#466477 | #8055. Balance | ucup-team2307# | WA | 119ms | 12024kb | C++20 | 7.3kb | 2024-07-07 21:10:41 | 2024-07-07 21:10:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back
const int N=2e5+100;
bool bridge[N];
vi num, st;
vector<vector<pii>> ed;
int Time;
template<class F>
int dfs(int at, int par, F& f) {
int me = num[at] = ++Time, e, y, top = me;
for (auto pa : ed[at]) if (pa.second != par) {
tie(y, e) = pa;
if (num[y]) {
top = min(top, num[y]);
if (num[y] < me)
st.push_back(e);
} else {
int si = sz(st);
int up = dfs(y, e, f);
top = min(top, up);
if (up == me) {
st.push_back(e);
f(vi(st.begin() + si, st.end()));
st.resize(si);
}
else if (up < me) st.push_back(e);
else { bridge[e]=true; }
}
}
return top;
}
template<class F>
void bicomps(F f) {
num.assign(sz(ed), 0);
rep(i,0,sz(ed)) if (!num[i]) dfs(i, -1, f);
}
vector<pii> edges;
struct UF {
vi e;
UF(int n) : e(n, -1) {}
bool sameSet(int a, int b) { return find(a) == find(b); }
int size(int x) { return -e[find(x)]; }
int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
bool join(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (e[a] > e[b]) swap(a, b);
e[a] += e[b]; e[b] = a;
return true;
}
};
int a[N],pref[N],suf[N];
int sz_vals;
int which_pref[N],which_suf[N];
pii goto_pref[N],goto_suf[N];
int siz[N];
int root;
int ind[N];
bool wrong_pref[N],wrong_suf[N];
UF dsu(0);
int dfs(int v,int p)
{
siz[v]=dsu.size(dsu.find(v));
for(auto[to,_]:ed[v])
if(to!=p)
siz[v]+=dfs(to,v);
if(root==-1) {
int my_pref = lower_bound(pref, pref + sz_vals, siz[v]) - pref;
if (my_pref == sz_vals || pref[my_pref] != siz[v]) my_pref = -1;
int my_suf = lower_bound(suf, suf + sz_vals, siz[v], greater<>()) - suf;
if (my_suf == sz_vals || suf[my_suf] != siz[v]) my_suf = -1;
bool found_pref = my_pref == 0, found_suf = my_suf == sz_vals - 1;
map<int, pii> prefs, sufs;
prefs[-1] = {-1, -1};
sufs[sz_vals] = {-1, -1};
goto_pref[v] = goto_suf[v] = {-1, -1};
for (auto [to, i]: ed[v])
if (to != p) {
if (which_pref[to] != -1 && which_pref[to] == my_pref - 1) found_pref = true, goto_pref[v] = {to, i};
if (which_suf[to] != -1 && which_suf[to] == my_suf + 1) found_suf = true, goto_suf[v] = {to, i};
if (which_pref[to] != -1 && sufs.count(which_pref[to] + 2)) {
root = v;
goto_pref[v] = {to, i};
goto_suf[v] = sufs[which_pref[to] + 2];
return siz[v];
}
if (which_suf[to] != -1 && prefs.count(which_suf[to] - 2)) {
root = v;
goto_suf[v] = {to, i};
goto_pref[v] = prefs[which_suf[to] - 2];
return siz[v];
}
if (which_pref[to] != -1)
prefs[which_pref[to]] = {to, i};
if (which_suf[to] != -1)
sufs[which_suf[to]] = {to, i};
}
which_pref[v] = found_pref ? my_pref : -1;
which_suf[v] = found_suf ? my_suf : -1;
if(which_pref[v]==-1)
{
pair<int,pii> best_pref={-1,{-1,-1}};
for (auto [to, i]: ed[v])
if (to != p && which_pref[to] != -1 && which_pref[to] > best_pref.fi)
best_pref={which_pref[to],{to,i}};
tie(which_pref[v],goto_pref[v])=best_pref;
wrong_pref[v]=true;
}
if(which_suf[v]==-1)
{
pair<int,pii> best_suf={-1,{-1,-1}};
for (auto [to, i]: ed[v])
if (to != p && which_suf[to] != -1 && which_suf[to] < best_suf.fi)
best_suf={which_suf[to],{to,i}};
tie(which_suf[v],goto_suf[v])=best_suf;
wrong_suf[v]=true;
}
}
return siz[v];
}
bool in_path[N];
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
num.clear();
st.clear();
ed.clear();
edges.clear();
for(int i=0;i<max(n,m);i++)
a[i]=pref[i]=suf[i]=which_pref[i]=which_suf[i]=siz[i]=ind[i]=bridge[i]=in_path[i]=wrong_pref[i]=wrong_suf[i]=0,
goto_pref[i]=goto_suf[i]={0,0};
sz_vals=0;
root=0;
Time=0;
ed.resize(n);
edges.resize(m);
for(int i=0;i<m;i++)
{
int x,y;
cin>>x>>y;
x--,y--;
edges[i]={x,y};
ed[x].pb({y,i});
ed[y].pb({x,i});
}
bicomps([](const auto&){});
dsu=UF(n);
for(int i=0;i<m;i++)
if(!bridge[i])
{
auto[x,y]=edges[i];
dsu.join(x,y);
}
ed.clear();
ed.resize(n);
for(int i=0;i<m;i++) if(bridge[i]) {
auto[x,y]=edges[i];
ed[dsu.find(x)].pb({dsu.find(y), i}),
ed[dsu.find(y)].pb({dsu.find(x), i});
}
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
vector<pii> vals;
for(int i=0;i<n;i++)
if(vals.empty()||vals.back().fi!=a[i])
vals.pb({a[i],1});
else
vals.back().se++;
sz_vals=sz(vals);
pref[0]=vals[0].se;
for(int i=1;i<sz(vals);i++)
pref[i]=pref[i-1]+vals[i].se;
suf[sz(vals)-1]=vals[sz(vals)-1].se;
for(int i=sz(vals)-2;i>=0;i--)
suf[i]=suf[i+1]+vals[i].se;
root=-1;
dfs(dsu.find(0),-1);
if(root==-1)
{
cout<<"No\n";
continue;
}
vector<int> path{root};
int v=root;
while(true)
{
auto[to,i]=goto_pref[v];
if(i==-1)
break;
if(!wrong_pref[to]) {
in_path[i] = true;
path.pb(to);
}
v=to;
}
reverse(all(path));
v=root;
while(true)
{
auto[to,i]=goto_suf[v];
if(i==-1)
break;
if(!wrong_suf[to]) {
in_path[i] = true;
path.pb(to);
}
v=to;
}
assert(sz(path)==sz(vals));
for(int i=0;i<m;i++) if(!in_path[i]) {
auto[x,y]=edges[i];
dsu.join(x,y);
}
for(int i=0;i<sz(path);i++)
ind[dsu.find(path[i])]=i;
cout<<"Yes\n";
for(int i=0;i<n;i++)
cout<<vals[ind[dsu.find(i)]].fi<<" ";
cout<<"\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 12024kb
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 1 2 2 Yes 2 2 1 1 1 No
result:
ok ok (5 test cases)
Test #2:
score: -100
Wrong Answer
time: 119ms
memory: 9780kb
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...
output:
Yes 2 2 3 1 No No No No Yes 2 1 1 1 No No No No No No No No Yes 1 3 1 1 1 No Yes 2 1 No Yes 2 1 No No No No No No No No No Yes 1 1 1 2 No No No No No No No Yes 1 1 1 1 2 Yes 1 2 1 1 No No No No Yes 3 1 3 3 2 Yes 1 2 1 1 No No Yes 2 2 1 No No No No No No No No No No No No No No No No No Ye...
result:
wrong answer ans finds an answer, but out doesn't (test case 3)