QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #330105 | #8055. Balance | ucup-team266# | WA | 85ms | 13884kb | C++14 | 6.6kb | 2024-02-17 12:30:48 | 2024-02-17 12:30:48 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef array<int, 3> ai3;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int Mod = 998244353;
inline int sign(int a){ return (a&1) ? (Mod-1) : 1; }
inline void uadd(int &a, int b){ a += b-Mod; a += (a>>31) & Mod; }
inline void usub(int &a, int b){ a -= b, a += (a>>31) & Mod; }
inline void umul(int &a, int b){ a = (int)(1ll * a * b % Mod); }
inline int add(int a, int b){ a += b-Mod; a += (a>>31) & Mod; return a; }
inline int sub(int a, int b){ a -= b, a += (a>>31) & Mod; return a; }
inline int mul(int a, int b){ a = (int)(1ll * a * b % Mod); return a; }
int qpow(int b, ll p){ int ret = 1; while(p){ if(p&1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
const int fN = 100;
int fact[fN], invfact[fN], pw2[fN], invpw2[fN], inv[fN];
void initfact(int n){
pw2[0] = 1; for(int i = 1; i <= n; ++i) pw2[i] = mul(pw2[i-1], 2);
invpw2[0] = 1; for(int i = 1; i <= n; ++i) invpw2[i] = mul(invpw2[i-1], (Mod+1) / 2);
fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i-1], i);
invfact[n] = qpow(fact[n], Mod-2); for(int i = n; i > 0; --i) invfact[i-1] = mul(invfact[i], i);
for(int i = 1; i <= n; ++i) inv[i] = mul(invfact[i], fact[i-1]);
}
int binom(int n, int m){ return (m < 0 || m > n) ? 0 : mul(fact[n], mul(invfact[m], invfact[n-m])); }
const double pi = acos(-1);
inline void chmax(int &a, int b){ (b>a) ? (a=b) : 0; }
inline void chmin(int &a, int b){ (b<a) ? (a=b) : 0; }
int n, ce;
vector<pii> g[100100];
int sp = 0, stk[100100], cdfn = 0, dfn[100100], low[100100];
int bel[100100], cc = 0;
void tarjan(int u, int lst){
low[u] = dfn[u] = cdfn++;
stk[sp++] = u;
for(auto p : g[u]){
int t = p.first;
if(p.second == lst) continue;
if(dfn[t] >= 0){
chmin(low[u], dfn[t]);
} else {
tarjan(t, p.second);
chmin(low[u], low[t]);
}
}
if(low[u] == dfn[u]){
do{
bel[stk[--sp]] = cc;
}while(stk[sp] != u);
++cc;
}
}
int m;
int cnt[100100], precnt[100100], sufcnt[100100];
vi tg[100100];
int w[100100], sz[100100];
int sid[100100], pid[100100], pre[100100], suf[100100], preson[100100], sufson[100100];
void dfs0(int u, int par){
sz[u] = w[u];
for(auto t : tg[u]){
if(t == par) continue;
dfs0(t, u);
sz[u] += sz[t];
}
{
int lb = 1, ub = m;
while(lb <= ub){
int mid = (lb+ub) / 2;
if(precnt[mid] <= sz[u])
lb = mid+1;
else
ub = mid-1;
}
pid[u] = ub;
if(precnt[pid[u]] == sz[u]){
if(pid[u] == 1)
pre[u] = u;
else {
for(auto t : tg[u])
if(pid[t] == pid[u] - 1 && pre[t] >= 0)
pre[u] = u, preson[u] = t;
}
} else {
for(auto t : tg[u])
if(pid[t] == pid[u] && pre[t] >= 0)
pre[u] = pre[t];
}
}
{
int lb = 1, ub = m;
while(lb <= ub){
int mid = (lb+ub) / 2;
if(sufcnt[mid] <= sz[u])
ub = mid-1;
else
lb = mid+1;
}
sid[u] = lb;
if(sufcnt[sid[u]] == sz[u]){
if(sid[u] == m)
suf[u] = u;
else {
for(auto t : tg[u])
if(sid[t] == sid[u] + 1 && suf[t] >= 0)
suf[u] = suf[t], sufson[u] = t;
}
} else {
for(auto t : tg[u])
if(sid[t] == sid[u] && suf[t] >= 0)
suf[u] = suf[t];
}
}
//cout << u << ": " << sz[u] << ": " << pid[u] << " " << pre[u] << "; " << sid[u] << " " << suf[u] << "\n";
}
int mark[100100];
void dfs1(int u, int par){
for(auto t : tg[u]){
if(t == par) continue;
if(!mark[t]) mark[t] = mark[u];
dfs1(t, u);
}
}
void solve(){
cin >> n >> ce;
rep(i, n) g[i].clear(), tg[i].clear();
rep(i, ce){
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(make_pair(v, i));
g[v].push_back(make_pair(u, i));
}
fill(cnt, cnt + n + 1, 0);
vi xs;
rep(i, n){
int a;
cin >> a;
++cnt[a];
}
for(int i = 1; i <= n; ++i) if(cnt[i]) xs.push_back(i);
sort(xs.begin(), xs.end());
xs.resize(m = (int)(unique(xs.begin(), xs.end()) - xs.begin()));
for(int i = 1; i <= n; ++i) if(cnt[i]) precnt[(int)(lower_bound(xs.begin(), xs.end(), i) - xs.begin() + 1)] = cnt[i];
precnt[0] = precnt[m+1] = 0;
for(int i = 0; i <= m+1; ++i) sufcnt[i] = precnt[i];
for(int i = 1; i <= m; ++i) precnt[i] += precnt[i-1];
for(int i = m; i >= 1; --i) sufcnt[i] += sufcnt[i+1];
//cout << "pre: ";
//for(int i = 1; i <= m; ++i) cout << precnt[i] << " ";
//cout << "\n";
//cout << "suf: ";
//for(int i = 1; i <= m; ++i) cout << sufcnt[i] << " ";
//cout << "\n";
cdfn = sp = cc = 0;
fill(dfn, dfn + n, -1);
tarjan(0, -1);
//cout << "bel: ";
//rep(i, n) cout << bel[i] << " ";
//cout << endl;
fill(pre, pre + n, -1), fill(suf, suf + n, -1);
rep(i, n) for(auto p : g[i]){
int t = p.first;
if(bel[t] != bel[i])
tg[bel[i]].push_back(bel[t]);
}
fill(w, w + cc, 0);
rep(i, n) ++w[bel[i]];
dfs0(0, -1);
fill(mark, mark + n, 0);
bool ok = 0;
if(pre[0] >= 0){
int u = 0;
for(int i = m; i >= 1; --i){
//cout << "mark " << u << " " << i << endl;
mark[u] = i;
if(i > 1)
u = pre[preson[u]];
}
ok = 1;
} else if(suf[0] >= 0){
int u = 0;
for(int i = 1; i <= m; ++i){
mark[u] = i;
if(i < m)
u = suf[sufson[u]];
}
ok = 1;
} else {
static int tmp[100100];
fill(tmp, tmp + m + 1, -1);
for(auto t : tg[0]){
if(suf[t] >= 0 && sid[t] - 2 >= 1 && tmp[sid[t] - 2] >= 0){
int u = tmp[sid[t] - 2];
for(int i = sid[t] - 2; i >= 1; --i){
mark[u] = i;
if(i > 1)
u = pre[preson[u]];
}
mark[0] = sid[t] - 1;
u = suf[t];
for(int i = sid[t]; i <= m; ++i){
mark[u] = i;
if(i < m)
u = suf[sufson[u]];
}
ok = 1;
break;
}
if(pre[t] >= 0)
tmp[pid[t]] = pre[t];
}
fill(tmp, tmp + m + 1, -1);
for(auto t : tg[0]){
if(ok) break;
if(pre[t] >= 0 && pid[t] + 2 <= m && tmp[pid[t] + 2] >= 0){
int u = pre[t];
for(int i = pid[t]; i >= 1; --i){
mark[u] = i;
if(i > 1)
u = pre[preson[u]];
}
mark[0] = pid[t] + 1;
u = tmp[pid[t] + 2];
for(int i = pid[t] + 2; i <= m; ++i){
mark[u] = i;
if(i < m)
u = suf[sufson[u]];
}
ok = 1;
break;
}
if(suf[t] >= 0)
tmp[sid[t]] = suf[t];
}
}
dfs1(0, -1);
if(ok){
cout << "Yes\n";
rep(i, n) cout << xs[mark[bel[i]] - 1] << " ";
cout << "\n";
} else
cout << "No\n";
//cout << "--------" << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 12660kb
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 1 2 3 4 5 No Yes 2 3 2 2 1 Yes 2 2 1 1 1 No
result:
ok ok (5 test cases)
Test #2:
score: -100
Wrong Answer
time: 85ms
memory: 13884kb
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 Yes 1 1 1 No No Yes 2 1 1 1 No No Yes 1 1 Yes 1 1 Yes 1 1 Yes 1 1 1 1 No Yes 1 1 1 1 1 Yes 1 3 1 1 1 Yes 1 1 1 Yes 1 2 Yes 1 1 1 1 1 Yes 1 2 No Yes 1 1 Yes 1 1 1 Yes 1 1 Yes 1 1 1 1 Yes 1 1 Yes 2 2 2 2 2 Yes 1 1 1 1 1 Yes 1 1 Yes 1 1 1 2 No Yes 1 1 No Yes 1 1 N...
result:
wrong answer 2-th smallest numbers are not same (test case 96)