QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #334023 | #8055. Balance | wtz2333 | WA | 110ms | 16260kb | C++17 | 6.5kb | 2024-02-21 00:16:48 | 2024-02-21 00:16:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
std::vector<pair<int,int>> e[maxn];
std::vector<int> c[maxn];
int dfn[maxn],low[maxn];
int bel[maxn],bel_siz[maxn];
int s[maxn],cnt,top,tot;
std::vector<vector<int>> ans;
void form(int x){
int now = 0;
tot ++;
do{
now = s[top --];
bel[now] = tot;
bel_siz[tot] ++;
c[tot].push_back(now);
}while(now != x);
}
void tarjan(int x,int now){
dfn[x] = low[x] = ++cnt;
s[++ top] = x;
for(auto [v,_]:e[x]){
if(_ == now)continue;
if(!dfn[v]){
tarjan(v,_);
low[x] = min(low[x],low[v]);
if(low[v] > dfn[x]){
form(v);
}
}else low[x] = min(low[x],dfn[v]);
}
}
void clear(int x){
cnt = tot = top = 0;
for(int i = 1;i <= x;i ++){
s[i] = bel[i] = dfn[i] = low[i] = bel_siz[i] = 0;
e[i].clear();
c[i].clear();
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T --){
int n,m;
cin >> n >> m;
clear(n);
for(int i = 1;i <= m;i ++){
int u,v;
cin >> u >> v;
e[u].push_back({v,i});
e[v].push_back({u,i});
}
for(int i = 1;i <= n;i ++){
if(dfn[i] == 0){
tarjan(i,0);
form(i);
}
}
int nn = tot;
vector<vector<int>> g(n + 1);
for(int i = 1;i <= n;i ++){
for(auto [v,_]:e[i]){
if(bel[i] != bel[v]){
g[bel[i]].push_back(bel[v]);
}
}
}
vector<int> a(n),b,p(n + 1);
std::vector<int> cnta(n + 1);
for(int i = 0;i < n;i ++) {
cin >> a[i];
cnta[a[i]] ++;
}
sort(a.begin(),a.end());
for(int i = 0;i < n;i ++) {
p[a[i]] = i + 1;
}
b = a;
reverse(b.begin(),b.end());
vector<array<int,2>> dp(nn + 1),dp_from(nn + 1);
vector<int> siz(nn + 1),f(nn + 1);
auto dfs = [&](auto self,int x,int fa) -> void {
siz[x] = bel_siz[x];
f[x] = fa;
for(auto v:g[x]){
if(v == fa)continue;
self(self,v,x);
siz[x] += siz[v];
}
for(auto v:g[x]){ // low -> high
if(v == fa)continue;
if(dp[v][0]){
int val1 = a[siz[v]];
int val2 = a[siz[x] - 1];
if(val1 == val2){
dp[x][0] = 1;
dp_from[x][0] = v;
}
}
}
for(auto v:g[x]){ // high -> low
if(v == fa)continue;
if(dp[v][1]){
int val1 = b[siz[v]];
int val2 = b[siz[x] - 1];
if(val1 == val2){
dp[x][1] = 1;
dp_from[x][1] = v;
}
}
}
dp[x][0] = cnta[a[0]] >= siz[x] ? 1 : dp[x][0];
dp[x][1] = cnta[b[0]] >= siz[x] ? 1 : dp[x][1];
// cerr << x << " "<< siz[x] << " " << dp[x][0] << " " << dp[x][1] << "\n";
};
dfs(dfs,1,0);
// cerr << nn << "\n";
std::vector<int> vis(nn + 1);
int ls = -1,rs = -1;
int flag = 0;
for(int i = 1;i <= nn;i ++){
std::vector<pair<int,int>> tmp;
for(auto v:g[i]){
if(v == f[i])continue;
if(dp[v][1]){
tmp.push_back({siz[v],v});
}
}
sort(tmp.begin(),tmp.end());
for(auto v:g[i]){
if(v == f[i])continue;
if(dp[v][0]){
int val = a[siz[v]];
int rev = p[val] - siz[v];
pair<int,int> other = {n - siz[v] - rev,0};
auto t = lower_bound(tmp.begin(),tmp.end(),other);
// cerr << i << " " << v << " " << rev << " " << siz[v] << "\n";
if(t != tmp.end()){
if(t->second == v){
t ++;
}
if(t != tmp.end()){
ls = v;
rs = t->second;
flag = 1;
break;
}
}
}
}
if(flag)break;
}
// for(int i = 1;i <= n;i ++)cerr << bel[i] << " \n"[i == n];
if(dp[1][0])flag = 1,ls = 1;
if(dp[1][1])flag = 1,rs = 1;
if(flag){
int LS = ls,RS = rs;
std::vector<int> ans(n + 1);
cout << "Yes\n";
int other = ls > 0 ? a[siz[ls]] : 0;
// cerr << "!!!!!\n";
while(ls > 0){
vis[ls] = 1;
ls = dp_from[ls][0];
}
auto dfs1 = [&](auto self,int x,int fa,int col) -> void {
for(auto v:c[x]){
// cerr << v << " " << col << "\n";
ans[v] = col;
}
for(auto v:g[x]){
if(v == fa)continue;
if(vis[v])self(self,v,x,a[siz[v] - 1]);
else self(self,v,x,col);
}
};
if(LS > 0)dfs1(dfs1,LS,f[LS],a[siz[LS] - 1]);
while(rs > 0){
vis[rs] = 1;
rs = dp_from[rs][1];
}
auto dfs2 = [&](auto self,int x,int fa,int col) -> void {
for(auto v:c[x]){
// cerr <<bel[x] << " " << v << " " << col << "\n";
ans[v] = col;
}
for(auto v:g[x]){
if(v == fa)continue;
if(vis[v])self(self,v,x,b[siz[v] - 1]);
else self(self,v,x,col);
}
};
// cerr << RS << "\n";
if(RS > 0)dfs2(dfs2,RS,f[RS],b[siz[RS] - 1]);
for(int i = 1;i <= n;i ++)if(!ans[i]) ans[i] = other;
for(int i = 1;i <= n;i ++)cout << ans[i] << " \n"[i == n];
}else {
cout << "No\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15424kb
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 1 2 2 3 Yes 2 2 1 1 1 No
result:
ok ok (5 test cases)
Test #2:
score: -100
Wrong Answer
time: 110ms
memory: 16260kb
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 1 3 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 2 1 Yes 1 1 1 1 1 Yes 2 1 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 2 1 1 No Yes 1 1 No Yes 1 1 No No No Yes 1 1 2 1 1 Ye...
result:
wrong answer 3-th smallest numbers are not same (test case 76)