QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#314985#895. ColorCharlieVinnieWA 1ms4148kbC++173.5kb2024-01-26 16:40:342024-01-26 16:40:35

Judging History

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

  • [2024-01-26 16:40:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4148kb
  • [2024-01-26 16:40:34]
  • 提交

answer

#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#define debuga(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std; typedef long long ll;
// N is the number of vertices, M is the number of edges you're about to add
// cst_type is what you think it is
template<int N,int M,typename cst_type=int>
class Dinic{
    int n,S,T,head[N],nxt[M*2],to[M*2],tot,q[N],h,t,dep[N],now[N]; cst_type cap[M*2],maxflow;
    bool bfs(){
        h=t=0; q[t++]=S; For(i,1,n) dep[i]=0; ; dep[S]=1; now[S]=head[S];
        while(h<t){
            int u=q[h++]; for(int e=head[u];e;e=nxt[e]){
                if(cap[e]==0) continue; ; int v=to[e];
                if(!dep[v]) { dep[v]=dep[u]+1; now[v]=head[v]; q[t++]=v; if(v==T) return true; }
            }
        } return false;
    }
    cst_type dfs(int u,cst_type flow){
        if(u==T) return flow; ; cst_type fw=0;
        for(int& e=now[u];e;e=nxt[e]){
            if(cap[e]==0) continue; ; int v=to[e]; if(dep[v]!=dep[u]+1) continue;
            cst_type res=dfs(v,min(flow,cap[e])); if(res==0) { dep[v]=0; continue; }
            cap[e]-=res; cap[e^1]+=res; fw+=res; flow-=res; if(flow==0) break;
        } return fw;
    }
public:
    void init(int _n) { n=_n; tot=1; } 
    void clear(int _n) { For(i,1,n) head[i]=0; ; maxflow=0; n=_n; tot=1; }
    int add_edge(int x,int y,cst_type z) { nxt[++tot]=head[x]; head[x]=tot; to[tot]=y; cap[tot]=z; nxt[++tot]=head[y]; head[y]=tot; to[tot]=x; cap[tot]=0; return tot-1; }
    cst_type solve(int _S,int _T,cst_type inf=numeric_limits<cst_type>::max()){
        if(!n||tot%2==0) { cerr<<"INIT YOUR DINIC!!!!!!!!!!!!"<<endl; exit(-1); }
        S=_S; T=_T; while(bfs()) { cst_type res=-1; while((res=dfs(S,inf))!=0) maxflow+=res; } ; return maxflow;
    }
    cst_type flowing(int e) { return cap[e^1]; }
    vector<int> get_cut() { bfs(); vector<int> res; for(int e=2;e<=tot;e+=2) if(dep[to[e^1]]&&!dep[to[e]]) res.push_back(e); ; return res; }
};
constexpr int N=210;
int n,m,a[N][N],vis[N][N],id[N][N]; Dinic<N*2,N*4> G;
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    cin>>n>>m; if(~m&1) return cout<<"No\n",0;
    For(i,1,n) For(j,i+1,n){
        cin>>a[i][j],a[j][i]=a[i][j];
        if(vis[i][a[i][j]]) return cout<<"No\n",0; else vis[i][a[i][j]]=1;
        if(vis[j][a[i][j]]) return cout<<"No\n",0; else vis[j][a[i][j]]=1;
    }
    while(n<m+1){
        debug(n);
        int S=m+n+2,T=m+n+3; G.clear(T);
        For(i,1,m) G.add_edge(S,i,1);
        For(i,1,n) G.add_edge(m+i,T,1);
        G.add_edge(m+n+1,T,m-n);
        For(i,1,m){
            int cc=0; For(j,1,n) if(!vis[j][i]) id[i][j]=G.add_edge(i,m+j,1); else cc++,id[i][j]=0;
            if(n-cc/2!=(m+1)/2) G.add_edge(i,m+n+1,1);
        }
        if(G.solve(S,T)!=m) return cout<<"No\n",0;
        For(i,1,m) For(j,1,n) if(!vis[j][i]&&G.flowing(id[i][j])) a[n+1][j]=a[j][n+1]=i,vis[n+1][i]=vis[j][i]=1;
        n++; For(i,1,n) debuga(a[i],1,n);
    }
    cout<<"Yes\n";
    For(i,1,m+1) For(j,i+1,m+1) cout<<a[i][j]<<" \n"[j==m+1];
    return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE

// Started Coding On: January 26 Fri, 16 : 07 : 13

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

input:

4 5
1 2 3
3 2
1

output:

No

result:

ok ok

Test #3:

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

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

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: 0
Accepted
time: 0ms
memory: 3728kb

input:

3 9
2 8
4

output:

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

result:

ok ok

Test #6:

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

input:

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

output:

No

result:

ok ok

Test #7:

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

input:

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

output:

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

result:

ok ok

Test #8:

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

input:

2 9
6

output:

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

result:

ok ok

Test #9:

score: 0
Accepted
time: 1ms
memory: 3704kb

input:

7 7
2 5 6 1 7 4
7 5 6 4 3
3 2 1 6
4 2 1
3 7
5

output:

Yes
2 5 6 1 7 4 3
7 5 6 4 3 1
3 2 1 6 4
4 2 1 7
3 7 5
5 6
2

result:

ok ok

Test #10:

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

input:

7 7
2 4 5 6 1 7
3 4 5 6 1
6 1 7 2
7 2 3
3 4
5

output:

Yes
2 4 5 6 1 7 3
3 4 5 6 1 7
6 1 7 2 5
7 2 3 1
3 4 2
5 4
6

result:

ok ok

Test #11:

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

input:

4 11
1 3 9
9 4
7

output:

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

result:

ok ok

Test #12:

score: 0
Accepted
time: 1ms
memory: 3764kb

input:

1 11

output:

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

result:

ok ok

Test #13:

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

input:

82 199
70 77 112 105 155 100 170 32 185 179 197 164 145 63 166 50 160 30 88 196 2 64 144 42 35 96 27 85 128 44 54 110 175 80 21 154 189 125 86 74 131 106 19 114 18 133 40 13 184 82 89 135 182 117 59 92 137 14 188 20 95 121 183 130 11 46 113 156 153 65 199 56 194 123 52 51 36 49 5 24 34
49 84 77 127 ...

output:

No

result:

wrong answer Jury has the answer but participant has not