QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#368318#8055. Balanceucup-team2219WA 77ms5888kbC++237.5kb2024-03-26 23:59:112024-03-26 23:59:12

Judging History

你现在查看的是最新测评结果

  • [2024-03-26 23:59:12]
  • 评测
  • 测评结果：WA
  • 用时：77ms
  • 内存：5888kb
查看
  • [2024-03-26 23:59:11]
  • 提交

answer

/*
 * Author       : YangDavid
 * Created Time : 2019年09月13日 星期五 11时55分25秒
 * Submit Link  : BZOJ 1718 (https://darkbzoj.tk/problem/1718)

 题意：给一个无向联通图，问至少加入几条边能使其变为边双联通图。
 题解：将原图用 Tarjan edge-BCC 缩点得到一棵树，则答案为 (leaf + 1) / 2
 */
#include <bits/stdc++.h>

#ifdef LOCAL
// #include "cp_debug.h"
#define debug(...) 42
#else
#define debug(...) 42
#endif
#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 namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;


template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
    read(first);
    read(args...);
}
template<typename T> void write(T x) {
    if(x > 9) write(x/10);
    putchar(x%10 + '0');
}

const int N = 100300, M = 200300;
// tarjan edge biconnected component
// INPUT -- user takes care of clearing these, then tarjan() takes care of the rest.
int n, m;
vector<pii> G[N];
// INTERMEDIARY
int pre[N], low[N], dfsClock;
// OUTPUT
int isBridge[M];
int eccno[N], eccCnt;
vector<int> nG[N];

void dfs1(int u, int fa) {
    low[u] = pre[u] = ++dfsClock;
    for(auto [v, e]: G[u]) {
        if(!pre[v]) {
            dfs1(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] > pre[u])
                isBridge[e] = true;
        } else if(v != fa && pre[v] < pre[u])
            low[u] = min(low[u], pre[v]);
    }
}

void dfs2(int u, int fa) { 
    eccno[u] = eccCnt;
    for(auto i: G[u]) 
        if(!isBridge[i.second] && i.first != fa && !eccno[i.first])
            dfs2(i.first, u);
}


void tarjan() { // 确保上面的变量均已经定义
    dfsClock = eccCnt = 0;
    memset(pre, 0, sizeof(int)*(n+1));
    memset(low, 0, sizeof(int)*(n+1));
    memset(isBridge, 0, sizeof(int)*(m+1));
    memset(eccno, 0, sizeof(int)*(n+1));

    dfs1(1, -1);
    for(int i = 1; i <= n; ++i) if(!eccno[i]) {
        eccCnt++;
        nG[eccCnt].clear();
        dfs2(i, -1);
    }
    for(int i = 1; i <= n; ++i) for(auto j: G[i]) {
        if(eccno[i] != eccno[j.first]) {
            nG[eccno[i]].push_back(eccno[j.first]);
        }
    }
}

struct State {
    pii rk1{}, rk2{};
    void update(pii x) {
        if(x == rk1 || x == rk2) return;
        if(x <= rk2) return;
        if(x <= rk1) { rk2 = x; return; }
        rk2 = rk1;
        rk1 = x;
    }
    tuple<int,int,int> combine(const State &rhs) const {
        if(rk1.first == 0 || rhs.rk1.first == 0 || rk1.second != rhs.rk1.second) {
            return {rk1.first + rhs.rk1.first, 1, 1};
        }
        tuple<int,int,int> ret = max(make_tuple(rk1.first, 1, 0), make_tuple(rhs.rk1.first, 0, 1));
        if(rhs.rk2.first == 0 || rhs.rk2.second != rk1.second) {
            ret = max(ret, make_tuple(rk1.first + rhs.rk2.first, 1, 0));
        }
        if(rk2.first == 0 || rk2.second != rhs.rk1.second) {
            ret = max(ret, make_tuple(rk2.first + rhs.rk1.first, 0, 1));
        }
        return ret;
    }
};
void solve() {
    read(n, m);
    rep(i, 1, m+1) {
        int u, v; // 注意存图方式
        read(u, v);
        G[u].emplace_back(v, i);
        G[v].emplace_back(u, i);
    }
    vi a(n+1);
    rep(i, 1, n+1) read(a[i]);
    tarjan();
    debug(vi(eccno+1, eccno+n+1));
    debug(vector<vi> (nG+1, nG+eccCnt+1));

    sort(a.begin()+1, a.end());
    vi siz(eccCnt+1, 0), valid_up(eccCnt+1, 0), valid_down(eccCnt+1, 0), eccSz(eccCnt+1, 0);
    rep(i,1,n+1) eccSz[eccno[i]]++;
    function<void(int,int)> dfs = [&](int u, int fath) {
        siz[u] = eccSz[u];
        for(auto v: nG[u]) if(v != fath) {
            dfs(v, u);
            siz[u] += siz[v];
            valid_up[v] = (a[siz[v]] != a[siz[v]+1]);
            valid_down[v] = (a[n-siz[v]] != a[n-siz[v]+1]);
        }
    };
    dfs(1, -1);
    debug(valid_up);
    debug(valid_down);


    vector<State> max_up(eccCnt+1), max_down(eccCnt+1);
    tuple<int,int,int> best = {-1,-1,-1};
    int best_vertex = -1;
    function<void(int,int)> dp = [&](int u, int fath) {
        for(auto v: nG[u]) if(v != fath) {
            dp(v, u);
            max_up[u].update({max_up[v].rk1.first + valid_up[v], v});
            max_down[u].update({max_down[v].rk1.first + valid_down[v], v});
        }
        auto cc = max_up[u].combine(max_down[u]);
        if(cc > best) {
            best = cc;
            best_vertex = u;
        }
    };
    dp(1, -1);

    rep(i,1,eccCnt+1) {
        debug(i,max_up[i].rk1, max_up[i].rk2);
        debug(i,max_down[i].rk1, max_down[i].rk2);
    }

    int num_changes = -1;
    vi a_distinct;
    rep(i, 1, n+1) {
        if(i == 1 || a[i-1] != a[i]) {
            a_distinct.emplace_back(a[i]);
            num_changes++;
        }
    }
    debug(num_changes, best);
    assert(num_changes >= get<0>(best));
    if(num_changes > get<0>(best)) {
        cout<<"No"<<'\n';
    } else {
        cout<<"Yes"<<'\n';
        vector<int> marked(eccCnt+1, -1), value(eccCnt+1, -1);
        auto [best_length, use_up_rk1, use_down_rk1] = best;
        auto [length_up, v_up] = use_up_rk1 ? max_up[best_vertex].rk1 : max_up[best_vertex].rk2;
        auto [length_down, v_down] = use_down_rk1 ? max_down[best_vertex].rk1 : max_down[best_vertex].rk2;
        assert(length_up + length_down == best_length);
        if(length_up > 0 && length_down > 0) {
            assert(v_up != v_down);
        }
        debug(length_up, v_up, length_down, v_down, best_vertex);
        marked[best_vertex] = a_distinct[length_up];
        if(length_up > 0) {
            int p1 = v_up, cp = length_up;
            if(max_up[p1].rk1.first < length_up) {
                marked[p1] = a_distinct[--cp];
            }
            while(max_up[p1].rk1.first > 0) {
                int np1 = max_up[p1].rk1.second;
                if(max_up[np1].rk1.first < max_up[p1].rk1.first) {
                    marked[np1] = a_distinct[--cp];
                }
                p1 = np1;
            }
        }
        if(length_down > 0) {
            int p2 = v_down, cp = length_up;
            if(max_down[p2].rk1.first < length_down) {
                marked[p2] = a_distinct[++cp];
            }
            while(max_up[p2].rk1.first) {
                int np2 = max_down[p2].rk1.second;
                if(max_up[np2].rk1.first < max_up[p2].rk1.first) {
                    marked[np2] = a_distinct[++cp];
                }
                p2 = np2;
            }
        }
        debug(marked);
        function<void(int,int,int)> dfs_mark = [&](int u, int fa, int cmark) {
            if(marked[u] != -1) cmark = marked[u];
            value[u] = cmark;
            for(auto v: nG[u]) if(v != fa) {
                dfs_mark(v, u, cmark);
            }
        };
        dfs_mark(1, -1, marked[best_vertex]);
        debug(value);
        rep(i,1,n+1) {
            cout<<value[eccno[i]]<<" \n"[i==n];
        }
    }


    rep(i, 1, n+1) G[i].clear();
    rep(i, 1, eccCnt+1) nG[i].clear();
}

int main() {
    int T; read(T);
    while(T--) solve();
    return 0;
}
源文件, 语言: C++23

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5752kb

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 2 2 3 1
Yes
2 2 1 1 1
No

result:

ok ok (5 test cases)

Test #2:

score: -100
Wrong Answer
time: 77ms
memory: 5888kb

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 1 1 2
No
Yes
1 1
No
Yes
1 1
No
No
No
Yes
1 1 1 1 2
Ye...

result:

wrong answer 3-th smallest numbers are not same (test case 145)
English 繁體中文 简体中文

伺服器時間: 2024-12-02 17:04:24 | 開源專案