QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#520800#895. Colordo_it_tomorrowWA 1ms5720kbC++143.7kb2024-08-15 15:52:262024-08-15 15:52:28

Judging History

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

  • [2024-08-15 15:52:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5720kb
  • [2024-08-15 15:52:26]
  • 提交

answer

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=205;
int n,m,c0[N],c1[N],c2[N],col[N][N],vis[N][N];
struct flow {
    static constexpr int inf = 1e9;
    static const int maxn = 4e2 + 10, maxm = maxn * maxn + maxn * 2 + 10;
    int N, S, T;
    int to[maxm * 2], val[maxm * 2], nxt[maxm * 2], fir[maxn], tot;
    inline flow(int N_, int S_, int T_) {
        N = N_, S = S_, T = T_;
    }
    inline void clear() {
        memset(fir, 0, sizeof(fir));
        tot = 1;
    }
    inline void add(int x, int y, int w, bool f = 1) {
        to[++tot] = y, val[tot] = w, nxt[tot] = fir[x], fir[x] = tot;
        if (f) add(y, x, 0, 0);
    }
    int hd[maxn], dep[maxn];
    inline bool bfs() {
        for (int i = 1; i <= N; i++)
            hd[i] = fir[i], dep[i] = -1;
        dep[S] = 0;
        std::queue<int> Q; Q.push(S);
        while (! Q.empty()) {
            int u = Q.front(); Q.pop();
            if (u == T) return true;
            for (int i = hd[u]; i; i = nxt[i])
                if (dep[to[i]] == -1 && val[i])
                    dep[to[i]] = dep[u] + 1, Q.push(to[i]);
        }
        return false;
    }
    inline int dfs(int u, int fl) {
        if (u == T)
            return fl;
        int ud = 0;
        for (int &i = hd[u]; i; i = nxt[i])
            if (dep[u] + 1 == dep[to[i]] && val[i]) {
                int k = dfs(to[i], std::min(fl - ud, val[i]));
                if (! k) dep[to[i]] = -1;
                ud += k, val[i] -= k, val[i ^ 1] += k;
                if (ud == fl)
                    return fl;
            }
        return ud;
    }
    inline int Dinic() {
        int ans = 0, f;
        while (bfs())
            while ((f = dfs(S, inf)) > 0)
                ans += f;
        return ans;
    }
};    

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    if(m%2==0){
        cout<<"No\n";
        return 0;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            cin>>col[i][j];
            col[j][i]=col[i][j];
            c2[col[i][j]]++;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(vis[col[i][j]][i]++){
                cout<<"No\n";
                return 0;
            }
        }
        for(int j=1;j<=m;j++){
            if(!vis[j][i]){
                c1[j]++;
            }
        }
    }
    for(int i=1;i<=m;i++){
        if(c1[i]+c2[i]>(m+1)/2){
            cout<<"No\n";
            return 0;
        }
    }
    int S=m*2+1,T=S+1;
    static flow f(m*2+2,S,T);
    while(n<=m){
        f.clear();
        for(int i=1;i<=m;i++){
            f.add(S,i,1);
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(!vis[i][j]){
                    f.add(i,m+j,1);
                }
            }
            for(int j=1;j<=2*c0[i];j++){
                f.add(i,n+m+1,1);
            }
        }
        for(int i=1;i<=n;i++){
            f.add(i+m,T,1);
        }
        for(int i=1;i<=m-n;i++){
            f.add(n+m+1,T,1);
        }
        f.Dinic();
        for(int i=1,to;i<=m;i++){
            for(int j=f.hd[i];j;j=f.nxt[j]){
                if(!f.val[j]){
                    to=f.to[j];
                }
            }
            if(to<=n+m){
                col[to-m][n+1]=i,vis[i][to-m]=vis[i][n+1]=1,c1[i]--;
            }
            else{
                c0[i]--,c1[i]++;
            }
        }
        n++;
    }
    cout<<"Yes\n";
    for(int i=1;i<=m+1;i++){
        for(int j=i+1;j<=m+1;j++){
            cout<<col[i][j]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5608kb

input:

3 5
1 2
4

output:

Yes
1 2 4 3 5 
4 3 5 2 
5 1 3 
2 1 
4 


result:

ok ok

Test #2:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

4 5
1 2 3
3 2
1

output:

No

result:

ok ok

Test #3:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

9 11
11 10 3 4 7 5 2 8
2 10 7 4 6 5 1
9 6 3 8 4 11
5 11 2 6 7
10 3 9 2
9 8 5
1 10
3

output:

No

result:

ok ok

Test #4:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

12 11
2 11 8 9 1 3 10 7 5 4 6
5 11 10 6 4 9 8 7 1 3
3 8 4 9 7 2 10 6 1
5 2 6 1 4 9 10 7
11 2 6 3 1 7 4
7 8 10 3 9 5
5 1 8 11 10
11 4 3 2
6 5 9
2 11
8

output:

Yes
2 11 8 9 1 3 10 7 5 4 6 
5 11 10 6 4 9 8 7 1 3 
3 8 4 9 7 2 10 6 1 
5 2 6 1 4 9 10 7 
11 2 6 3 1 7 4 
7 8 10 3 9 5 
5 1 8 11 10 
11 4 3 2 
6 5 9 
2 11 
8 


result:

ok ok

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 5720kb

input:

3 9
2 8
4

output:

Yes
2 8 7 5 9 1 6 0 4 
4 8 9 7 6 5 0 0 
9 7 6 5 2 3 0 
6 5 2 1 4 3 
8 3 4 1 2 
4 3 2 1 
9 7 8 
8 7 
9 


result:

wrong answer Integer parameter [name=color of edges] equals to 0, violates the range [1, 9]