QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#470788#895. ColorlhzawaRE 1ms6776kbC++143.4kb2024-07-10 16:26:192024-07-10 16:26:20

Judging History

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

  • [2024-07-10 16:26:20]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:6776kb
  • [2024-07-10 16:26:19]
  • 提交

answer

// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
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[maxn * 2], nxt[maxm * 2], fir[maxn], tot;
   inline flow(int N_, int S_, int T_) {
      N = N_, S = S_, T = T_;
      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;
   }
};
const int maxn = 2e2 + 10;
int col[maxn][maxn];
int vis[maxn][maxn], cnt[maxn][3];
int main() {
   int n, m; scanf("%d%d", &n, &m);
   for (int i = 1; i <= n; i++)
      for (int j = i + 1; j <= n; j++)
         scanf("%d", &col[i][j]), col[j][i] = col[i][j], cnt[col[i][j]][2]++;
   if (~ m & 1)
      return puts("No"), 0;
   int M = m + 1 >> 1;
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++)
         if (vis[col[i][j]][i]++)
            return puts("No"), 0;
      for (int j = 1; j <= m; j++)
         if (! vis[j][i])
            cnt[j][1]++;
   }
   for (int i = 1; i <= m; i++)
      if (cnt[i][2] + cnt[i][1] > M)
         return puts("No"), 0;
   for (int i = 1; i <= m; i++)
      cnt[i][0] = M - cnt[i][1] - cnt[i][2];
   while (n < m + 1) {
      int S, T;
      flow f(m * 2 + 2, S = m * 2 + 1, T = m * 2 + 2);
      for (int i = 1; i <= m; i++)
         f.add(S, i, 1), f.add(m + i, T, 1);
      for (int i = 1, hd = m + n + 1, fl = 0; i <= m; i++) {
         for (int j = 1; j <= n; j++) {
            if (! vis[i][j])
               f.add(i, m + j, 1);
         }
         for (int j = 2 * cnt[i][0]; j; j--) {
            f.add(i, hd, 1), fl++;
            if (fl == m - n + 1) fl = 0, hd++;
         }
      }
      f.Dinic();
      for (int i = 1; i <= m; i++) {
         int to = -1;
         for (int j = f.hd[i]; j; j = f.nxt[j])
            if (! f.val[j])
               to = f.to[j];
         if (to <= m + n)
            col[to - m][n + 1] = i, vis[i][to - m] = vis[i][n + 1] = 1, cnt[i][1]--;
         else
            cnt[i][0]--, cnt[i][1]++;
      }
      n++;
   }
   puts("Yes");
   for (int i = 1; i <= n; i++, puts(""))
      for (int j = i + 1; j <= n; j++)
         printf("%d ", col[i][j]);
   return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5
1 2
4

output:

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


result:

ok ok

Test #2:

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

input:

4 5
1 2 3
3 2
1

output:

No

result:

ok ok

Test #3:

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

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: 1ms
memory: 6776kb

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

input:

3 9
2 8
4

output:

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


result:

ok ok

Test #6:

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

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: 0ms
memory: 6476kb

input:

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

output:

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


result:

ok ok

Test #8:

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

input:

2 9
6

output:

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


result:

ok ok

Test #9:

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

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: 1ms
memory: 6500kb

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

input:

4 11
1 3 9
9 4
7

output:

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


result:

ok ok

Test #12:

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

input:

1 11

output:

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


result:

ok ok

Test #13:

score: -100
Runtime Error

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:


result: