QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#331199#8055. Balanceucup-team1600WA 142ms11836kbC++208.5kb2024-02-18 03:20:022024-02-18 03:20:03

Judging History

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

  • [2024-02-18 03:20:03]
  • 评测
  • 测评结果：WA
  • 用时：142ms
  • 内存：11836kb
查看
  • [2024-02-18 03:20:02]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

mt19937 rng(4242);

const int max_n = 1e5 + 42, max_m = 2e5 + 42, inf = 1000111222;

vector<pair<int, int> > g[max_n];
vector<int> g2[max_n];
map<int, vector<pair<int, int> > > g3[max_n];

vector <pii> edge[max_n];

bool bridge[max_m] = {}, used[max_n] = {};

int tin[max_n] = {}, timer = 0, low[max_n] = {};

inline int dfs (int v, int p_id = -1) {
    used[v] = 1;
    tin[v] = timer++;
    low[v] = inf;
    for (auto [to, id] : edge[v]) {
        if (id == p_id) {
            continue;
        }
        if (used[to]) {
            umin(low[v], tin[to]);
        }
        else {
            umin(low[v], dfs(to, id));
            if (low[to] > tin[v]) {
                bridge[id] = 1;
            }
        }
    }
    return low[v];
}

int comp[max_n], am_comp[max_n], cur_comp = 0;

void dfs2(int v, int p) {
    comp[v] = cur_comp;
    am_comp[comp[v]]++;
    for(auto& to : g[v])
        if(!bridge[to.se] && to.fi != p && comp[to.fi] == -1)
            dfs2(to.fi, v);
}

int subt[max_n];

int dfs3(int v, int p) {
    subt[v] = am_comp[v];
    for(auto& to : g2[v]) {
        if(to != p) subt[v] += dfs3(to, v);
    }
    return subt[v];
}

set<pair<int, int> > bad_edge;

int val[max_n];

void dfs4(int v, int p) {
//    cout << v << ' ' << val[v] << '\n';
    used[v] = true;
    for(auto& to : g2[v])
        if(to != p && !used[to] && !bad_edge.count({v, to})) {
            val[to] = val[v];
            dfs4(to, v);
        }
}

void solve() {
    int n, m;
    cin >> n >> m;
    bad_edge.clear();
    for(int i = 0; i < n; i++) {
        val[i] = -1;
        comp[i] = -1; am_comp[i] = 0;
        g[i].clear(); g2[i].clear(); g3[i].clear();
        edge[i].clear();
        used[i] = 0;
        tin[i] = low[i] = 0;
    }
    for(int i = 0; i < m; i++) bridge[i] = false;
    timer = 0;
    vector<pair<int, int> > edg;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        edg.pb({u, v});
        edge[u].pb({v, i});
        edge[v].pb({u, i});
        g[u].pb({v, i});
        g[v].pb({u, i});
    }
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(all(a));
    vector<pair<int, int> > b;
    for(int i = 0; i < n; i++) {
        int j = i;
        while(j + 1 < n && a[j + 1] == a[j]) j++;
        b.pb({a[i], j - i + 1});
        i = j;
    }
    vector<pair<int, bool> > transitions(n + 1, {-1, false});
    int cur_sum = 0;
    for(int i = 0; i < len(b); i++) {
        cur_sum += b[i].se;
        transitions[cur_sum] = {i + 1, true};
    }
    int cur_transition = 0;
    for(int i = 0; i <= n; i++) {
        if(transitions[i].se) cur_transition = transitions[i].fi;
        else transitions[i] = {cur_transition, false};
    }
//    for(int i = 0; i < n; i++) cout << transitions[i].fi << ' ' << transitions[i].se << '\n';
    dfs(0);
    cur_comp = 0;
    for(int i = 0; i < n; i++)
        if(comp[i] == -1) {
            dfs2(i, i);
            cur_comp++;
        }
    for(int i = 0; i < m; i++) {
        int u = comp[edg[i].fi], v = comp[edg[i].se];
        if(u != v) {
//            LOG(u, v);
            g2[u].pb(v);
            g2[v].pb(u);
        }
    }
//    for(int i = 0; i < n; i++) cout << comp[i] << ' ';
//    cout << '\n';
    dfs3(0, 0);
//    for(int i = 0; i < n; i++) cout << subt[i] << ' ';
//    cout << '\n';
    for(int i = 0; i < m; i++) {
        int u = comp[edg[i].fi], v = comp[edg[i].se];
        if(u != v) {
            if(subt[v] > subt[u]) swap(u, v);
            int size_v = subt[v], size_u = n - subt[v];
//            cout << v << ' ' << u << ' ' << size_v << ' ' << size_u << '\n';
            {
//                LOG(edg[i].fi, edg[i].se, v, u, transitions[size_v] - 1);
                //(v, transitions[size_v] - 1) -> (u, transitions[size_v])
                g3[v][transitions[size_v].fi - transitions[size_v].se].pb({u, transitions[size_v].fi});
            }
            {
//                LOG(edg[i].fi, edg[i].se, u, v, transitions[size_u] - 1);
                //(u, transitions[size_u] - 1) -> (v, transitions[size_u])
                g3[u][transitions[size_u].fi - transitions[size_u].se].pb({v, transitions[size_u].fi});
            }
        }
    }
    set<pair<pair<int, int>, int> > was;
    map<pair<int, int>, int> was_from;
    map<pair<pair<int, int>, int>, pair<pair<int, int>, int> > pr;
    queue<pair<pair<int, int>, int> > q;
    for(int i = 0; i < len(b); i++) {
        was.insert({{i, 0}, -1});
        q.push({{i, 0}, -1});
    }
    while(!q.empty()) {
        auto cr = q.front(); q.pop();
        int V = cr.fi.fi, MODE = cr.fi.se, FROM = cr.se;
        for(auto& to : g3[V][MODE]) {
            if(FROM != to.fi && !was.count({{to.fi, to.se}, FROM}) && was_from[{to.fi, to.se}] <= 2) {
                was_from[{to.fi, to.se}]++;
                was.insert({{to.fi, to.se}, V});
                q.push({{to.fi, to.se}, V});
                pr[{{to.fi, to.se}, V}] = cr;
            }
        }
    }
//    for(int i = 0; i < n; i++) cout << comp[i] << ' ';
//    cout << '\n';
    for(int i = 0; i < n; i++) used[i] = false;
    for(auto& x : was) {
        int V = x.fi.fi, MODE = x.fi.se, FROM = x.se;
        if(MODE == len(b) - 1) {
            vector<int> to_go_from;
            int cv = V, cmode = MODE, cfrom = FROM;
            val[cv] = b[cmode].fi;
            to_go_from.pb(cv);
//            LOG(b[cmode].fi);
            while(pr.count({{cv, cmode}, cfrom})) {
                int nv, nmode, nfrom;
                auto to = pr[{{cv, cmode}, cfrom}];
                nv = to.fi.fi, nmode = to.fi.se, nfrom = to.se;
                if(nmode != cmode) {
                    bad_edge.insert({cv, nv});
                    bad_edge.insert({nv, cv});
                }
                val[nv] = b[nmode].fi;
                to_go_from.pb(nv);
//                LOG(cv, cmode, cfrom);
//                LOG(nv, nmode, nfrom);
                cv = nv, cmode = nmode, cfrom = nfrom;
            }
            for(int i = 0; i < n; i++) used[i] = false;
            for(auto v : to_go_from) if(!used[v]) dfs4(v, v);
            cout << "Yes\n";
            for(int j = 0; j < n; j++) cout << val[comp[j]] << ' ';
            cout << '\n';
            return;
        }
    }
//    for(int i = 0; i < n; i++)
//        if(was.count({i, len(b) - 1})) {
//            int cv = i, cmode = len(b) - 1;
//            val[cv] = b[cmode].fi;
//            to_go_from.pb(cv);
//            LOG(cv, cmode);
//            while(pr.count({cv, cmode})) {
//                int nv, nmode;
//                tie(nv, nmode) = pr[{cv, cmode}];
//                if(nmode != cmode) {
//                    bad_edge.insert({cv, nv});
//                    bad_edge.insert({nv, cv});
//                    val[nv] = b[nmode].fi;
//                }
//                cv = nv; cmode = nmode;
//                LOG(cv, cmode);
//                to_go_from.pb(cv);
//            }
////            for(auto v : to_go_from) if(!used[v]) dfs4(v, v);
//            cout << "Yes\n";
//            for(int j = 0; j < n; j++) cout << val[comp[j]] << ' ';
//            cout << '\n';
//            return;
//        }
    cout << "No\n";
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;

    cin >> t;

    while (t--) solve();

}

/*
KIVI
*/
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 142ms
memory: 11836kb

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 
N...

result:

wrong answer ans finds an answer, but out doesn't (test case 96)
English 繁體中文 简体中文

Server Time: 2024-12-02 21:43:31 | OpenSource Project