QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#466494#8055. Balanceucup-team2307WA 119ms11776kbC++207.4kb2024-07-07 21:20:322024-07-07 21:20:35

Judging History

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

  • [2024-07-07 21:20:35]
  • 评测
  • 测评结果：WA
  • 用时：119ms
  • 内存：11776kb
查看
  • [2024-07-07 21:20:32]
  • 提交

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={int(1e9),{-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}};
            if(best_suf.fi>1e8) best_suf.fi=-1;
            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";
    }
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 9824kb

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)
English 繁體中文 简体中文

Server Time: 2024-12-02 16:06:12 | OpenSource Project