QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#640322#8055. BalanceMiniLongWA 43ms26344kbC++146.9kb2024-10-14 10:58:522024-10-14 10:58:52

Judging History

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

  • [2024-10-14 10:58:52]
  • 评测
  • 测评结果：WA
  • 用时：43ms
  • 内存：26344kb
查看
  • [2024-10-14 10:58:52]
  • 提交

answer

#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; ++i)
#define _req(i, x, y) for(int i = x; i >= y; --i)
#define _rev(i, u) for(int i = head[u]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define mst(f, i) memset(f, i, sizeof f)
using namespace std;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
typedef long long ll;
typedef pair<int, int> PII;
namespace fastio{
    #ifdef ONLINE_JUDGE
    char ibuf[1 << 20],*p1 = ibuf, *p2 = ibuf;
    #define get() p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++
    #else
    #define get() getchar()
    #endif
    template<typename T> inline void read(T &t){
        T x = 0, f = 1;
        char c = getchar();
        while(!isdigit(c)){
            if(c == '-') f = -f;
            c = getchar();
        }
        while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
        t = x * f;
    }
    template<typename T, typename ... Args> inline void read(T &t, Args&... args){
        read(t);
        read(args...);
    }
    template<typename T> void write(T t){
        if(t < 0) putchar('-'), t = -t;
        if(t >= 10) write(t / 10);
        putchar(t % 10 + '0');
    }
    template<typename T, typename ... Args> void write(T t, Args... args){
        write(t), putchar(' '), write(args...);
    }
    template<typename T> void writeln(T t){
        write(t);
        puts("");
    }
    template<typename T> void writes(T t){
        write(t), putchar(' ');
    }
    #undef get
};
using namespace fastio;
#define multitest() int T; read(T); _rep(tCase, 1, T)
namespace Calculation{
    const ll mod = 998244353;
    ll ksm(ll p, ll h){ll base = p % mod, res = 1; while(h){if(h & 1ll) res = res * base % mod; base = base * base % mod, h >>= 1ll;} return res;}
    void dec(ll &x, ll y){x = ((x - y) % mod + mod) % mod;}
    void add(ll &x, ll y){x = (x + y) % mod;}
    void mul(ll &x, ll y){x = x * y % mod;}
    ll sub(ll x, ll y){return ((x - y) % mod + mod) % mod;}
    ll pls(ll x, ll y){return ((x + y) % mod + mod) % mod;}
    ll mult(ll x, ll y){return x * y % mod;}
}
using namespace Calculation;
const int N = 2e5 + 5;
int n, m, a[N], pre[N], nxt[N], cnt[N], pcnt[N], scnt[N];
vector<PII> G[N];
int id, num, dfn[N], low[N], scc[N], siz[N];
int top, st[N];
void tarjan(int u, int fa){
    dfn[u] = low[u] = ++id, st[++top] = u;
    for(auto &[v, i] : G[u]){
        if(!dfn[v]) tarjan(v, i), low[u] = min(low[u], low[v]);
        else if(i != fa) low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]){
        num++;
        for(int x = 0; x != u; top--){
            x = st[top], scc[x] = num;
            siz[num]++;
        }
    }
}
vector<int> e[N];
bool dp[N][2];//0:pre 1:suf
int pfa[N], f[N], g[N], sum[N];
PII ans[N];
void dfs(int u, int fa){
    sum[u] = siz[u], pfa[u] = fa;
    for(auto &v : e[u]) if(v != fa) dfs(v, u), sum[u] += sum[v];
    set<PII> st;
    for(auto &v : e[u]){
        if(v == fa) continue;
        int pos = lower_bound(pcnt + 1, pcnt + 1 + n, sum[v]) - pcnt;
        // debug("u:%d v:%d pos:%d\n", u, v, pos);
        if(dp[v][0] && (pcnt[pos] == sum[v] && cnt[nxt[pos]] >= sum[u] - sum[v] || pcnt[pos] >= sum[u])){
            dp[u][0] = 1, f[u] = v;
        }
        pos = lower_bound(scnt + 1, scnt + 1 + n, sum[v]) - scnt; 
        if(dp[v][1] && (scnt[pos] == sum[v] && cnt[pre[n - pos + 1]] >= sum[u] - sum[v] || scnt[pos] >= sum[u])){
            dp[u][1] = 1, g[u] = v;
        }
        if(dp[v][1]) st.insert({sum[v], v});
    }
    for(auto &v : e[u]){
        if(v == fa || !dp[v][0]) continue;
        int pos = lower_bound(pcnt + 1, pcnt + 1 + n, sum[v]) - pcnt;
        int l = (sum[v] == pcnt[pos]) ? n - pcnt[nxt[pos]] : n - pcnt[pos];
        int r = (sum[v] == pcnt[pos]) ? n - pcnt[pos] : n - sum[v];
        auto it = st.lower_bound(make_pair(l, 0));
        if(it != st.end()){
            if((*it).se == v) it++;
            if(it != st.end() && (*it).fi <= r){
                ans[u] = {v, (*it).se};
                // debug("u:%d (%d,%d)\n", u, v, (*it).se);
            }
        }
    }
    int pos = lower_bound(pcnt + 1, pcnt + 1 + n, sum[u]) - pcnt;
    if(cnt[pos] == sum[u]) dp[u][0] = 1;
    pos = lower_bound(scnt + 1, scnt + 1 + n, sum[u]) - scnt;
    if(cnt[n - pos + 1] == sum[u]) dp[u][1] = 1;
    // debug("siz[%d]:%d (%d,%d)\n", u, sum[u], dp[u][0], dp[u][1]);
}
int col[N];
void dfs2(int u, int c){
    col[u] = c;
    for(auto &v : e[u]) if(!col[v]) dfs2(v, c);
}
void clr(){
    _rep(i, 1, n){
        col[i] = pfa[i] = f[i] = g[i] = sum[i] = dp[i][0] = dp[i][1] = 0, ans[i] = {0, 0};
        dfn[i] = low[i] = scc[i] = siz[i] = 0;
        pre[i] = nxt[i] = cnt[i] = pcnt[i] = scnt[i] = 0;
        G[i].clear(), e[i].clear();
    }
    id = num = 0;
}
int main(){
    multitest(){
        read(n, m);
        _rep(i, 1, m){
            int u, v; read(u, v);
            G[u].pb({v, i}), G[v].pb({u, i});
        }
        _rep(i, 1, n) read(a[i]), cnt[a[i]]++;
        _rep(i, 1, n) pre[i] = cnt[i - 1] ? i - 1 : pre[i - 1], pcnt[i] = cnt[i] + pcnt[i - 1];
        _req(i, n, 1) nxt[i] = cnt[i + 1] ? i + 1 : nxt[i + 1], scnt[i] = cnt[i] + scnt[i + 1];
        reverse(scnt + 1, scnt + 1 + n);
        tarjan(1, 0);
        _rep(i, 1, n) for(auto &[j, id] : G[i]) if(scc[i] != scc[j]) e[scc[i]].pb(scc[j]);
        dfs(1, 0);
        vector<PII> res;
        _rep(i, 1, n){
            if(ans[i].fi){
                // debug("fuck (%d,%d)\n", ans[i].fi, ans[i].se);
                int u = ans[i].fi;
                while(u) res.pb({u, sum[u] - sum[f[u]]}), u = f[u];
                reverse(res.begin(), res.end());
                u = ans[i].se; res.pb({i, n - sum[ans[i].fi] - sum[ans[i].se]});
                while(u) res.pb({u, sum[u] - sum[g[u]]}), u = g[u];
                break;
            }
        }
        if(res.empty() && dp[1][0]){
            int u = 1;
            while(u) res.pb({u, sum[u] - sum[f[u]]}), u = f[u];
            reverse(res.begin(), res.end());
        }
        if(res.empty() && dp[1][1]){
            int u = 1;
            while(u) res.pb({u, sum[u] - sum[g[u]]}), u = g[u];
        }
        if(res.empty()) puts("No");
        else{
            puts("Yes");
            int cur = 1;
            for(auto &i : res){
                while(!cnt[cur]) cur++;
                // if(cnt[cur] < i.se){
                    
                // }
                col[i.fi] = cur;
                cnt[cur] -= i.se;
            }
        // for(auto &i : res) debug("(%d,%d,col:%d) ", i.fi, i.se, col[i.fi]); debug("\n");
            for(auto &i : res) dfs2(i.fi, col[i.fi]);
            _rep(i, 1, n) writes(col[scc[i]]); puts("");
        }
        clr();
    }    
    return 0;
}
源文件, 语言: C++14

详细

Test #1:

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

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

result:

ok ok (5 test cases)

Test #2:

score: -100
Wrong Answer
time: 43ms
memory: 22236kb

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

服务器时间: 2024-12-02 15:46:13 | 开源项目