QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#797994	#7600. Minimums on the Edges	Cookie_Creamm	AC ✓	676ms	327460kb	C++23	2.8kb	2024-12-03 22:29:41	2024-12-03 22:29:41

Judging History

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

[2024-12-03 22:29:41]
评测

测评结果：AC
用时：676ms
内存：327460kb

查看

[2024-12-03 22:29:41]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vt vector
#define pb push_back
#define pii pair<int, int>
#define sz(dq) (int)dq.size()
#define forr(i, a, b) for(int i = a; i < b; i++)
#define fi first
#define se second
#define pll pair<ll, ll>
#define mpp make_pair
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ld long double

const ll mxn = 4e5 + 5, inf = 1e9, mod = 998244353, sq = 800, mxv = 1e6 + 5, pr = 37, mod2 = 1e9 + 9, mod3 = 998244353;
//const int x[4] = {0, -1, 0, 1};
 
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
//const char dir[4] = {'D', 'U', 'R', 'L'};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, s;
int cnt[(1 << 18)], dp[(1 << 18)][105];
pii trace[(1 << 18)][105];
int res[19];
bool ckmax(int &a, int b){
    if(a < b){
        a = b; return(1);
    }
    return(0);
}
void solve(){       
    cin >> n >> m >> s;
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v; --u; --v;
        cnt[(1 << u) | (1 << v)]++;
    }
    for(int i = 0; i < 18; i++){
        for(int j = 0; j < (1 << 18); j++){
            if((j >> i) & 1){
                cnt[j] += cnt[j ^ (1 << i)];
            }
        }
    }
    for(int i = 0; i < (1 << n); i++){
        for(int j = 0; j <= s; j++){
            dp[i][j] = -inf;
        }
    }
    dp[0][0] = 0;
    for(int i = 0; i < (1 <<  n); i++){
        int c = __builtin_popcount(i);
        for(int j = 0; j <= s; j++){
            if(dp[i][j] == -inf)continue;
            for(int k = 0; k < n; k++){
                if(!((i >> k) & 1)){
                    if(ckmax(dp[i | (1 << k)][j], dp[i][j])){
                        trace[i | (1 << k)][j] = mpp(i, j);
                    }
                }
            }
            if(j + c <= s){
                if(ckmax(dp[i][j + c], dp[i][j] + cnt[i])){
                    trace[i][j + c] = mpp(i, j);
                }
            }
        }  
    }
    pii state;
    int ans = -1;
    for(int i = 0; i <= s; i++){
        if(ckmax(ans, dp[(1 << n) - 1][i])){
            state = mpp((1 << n) - 1, i);
        }
    }
    
    while(state.fi != 0){
        pii cool = trace[state.fi][state.se];
        if(state.se != cool.se){
            for(int i = 0; i < n; i++){
                if((cool.fi >> i) & 1){
                    res[i]++; s--;
                }
            }
        }
        state = cool;
    }
    res[0] += s;
    for(int i = 0; i < n; i++)cout << res[i] <<  " ";
}
 
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("ARRAY.inp", "r", stdin);
    //freopen("ARRAY.out", "w", stdout);
    
    int tt; tt = 1;
    while(tt--){
        solve();
    }
    return(0);
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 8736kb

input:

output:

2 2 2 0

result:

ok answer = 6

Test #2:

score: 0

Accepted

time: 5ms

memory: 6884kb

input:

output:

3 2 2

result:

ok answer = 14

Test #3:

score: 0

Accepted

time: 5ms

memory: 7832kb

input:

output:

15 15 15 1 15

result:

ok answer = 122

Test #4:

score: 0

Accepted

time: 5ms

memory: 6692kb

input:

output:

2 0 2 2 0

result:

ok answer = 12

Test #5:

score: 0

Accepted

time: 5ms

memory: 6972kb

input:

output:

27 2 2 27 27

result:

ok answer = 170

Test #6:

score: 0

Accepted

time: 2ms

memory: 7936kb

input:

output:

6 6 6 6 6

result:

ok answer = 60

Test #7:

score: 0

Accepted

time: 2ms

memory: 8452kb

input:

output:

0 38 1 0 38

result:

ok answer = 154

Test #8:

score: 0

Accepted

time: 6ms

memory: 9340kb

input:

output:

0 0 0 0 1 1 1 1 0 0

result:

ok answer = 1415

Test #9:

score: 0

Accepted

time: 7ms

memory: 11092kb

input:

10 10000 83
7 9
6 4
3 6
7 5
2 5
10 7
10 7
7 10
6 5
3 9
2 6
9 10
8 2
6 2
10 1
3 9
4 2
9 5
2 10
6 3
10 5
5 9
6 2
1 4
8 9
7 6
2 5
7 8
10 4
2 1
2 9
7 10
2 7
2 5
9 10
10 8
4 1
10 8
2 5
3 10
6 7
6 3
5 8
10 2
6 10
6 3
9 5
6 2
8 5
8 2
8 10
2 8
5 10
5 2
10 3
8 6
3 1
3 2
8 7
3 7
8 2
9 7
5 9
5 3
7 5
2 6
6 9
8 ...

output:

8 8 8 8 8 8 9 8 9 9

result:

ok answer = 80726

Test #10:

score: 0

Accepted

time: 0ms

memory: 9380kb

input:

10 10000 28
8 3
7 5
10 9
6 2
1 9
4 7
4 7
7 1
10 6
10 5
5 3
8 3
3 1
3 1
8 1
4 7
5 6
4 10
3 2
4 8
2 4
9 7
8 7
10 9
9 10
2 1
6 1
7 1
2 8
5 10
1 4
5 8
1 3
8 3
4 3
9 2
5 1
4 6
10 1
10 2
5 4
9 3
10 2
5 9
2 1
7 4
1 8
4 8
3 9
9 6
3 6
5 1
2 7
4 3
2 8
8 10
1 7
4 1
3 9
1 2
1 9
8 4
9 5
1 5
6 4
1 6
6 7
2 7
10 4
...

output:

3 3 3 2 3 2 3 3 3 3

result:

ok answer = 26312

Test #11:

score: 0

Accepted

time: 3ms

memory: 9052kb

input:

output:

1 0 1 1 0 0 1 0 1 1

result:

ok answer = 3460

Test #12:

score: 0

Accepted

time: 6ms

memory: 9540kb

input:

10 10000 19
1 3
6 7
4 5
9 8
5 8
1 9
10 7
10 6
2 9
2 5
2 4
2 3
3 2
9 3
3 9
7 10
7 8
7 1
8 6
8 9
1 5
2 5
4 6
2 10
8 9
8 2
6 7
9 10
1 2
3 10
5 6
8 5
5 9
3 4
4 10
5 3
8 9
6 1
4 2
2 5
2 9
2 10
1 9
9 4
10 2
8 4
9 1
7 8
1 2
6 10
8 2
8 10
5 4
10 9
7 2
3 2
6 8
5 4
8 9
8 10
6 8
10 4
7 3
3 5
9 8
6 7
5 3
5 8
2 ...

output:

2 2 2 2 2 2 2 2 1 2

result:

ok answer = 18048

Test #13:

score: 0

Accepted

time: 178ms

memory: 327424kb

input:

output:

3 1 0 0 3 3 0 0 0 3 0 0 0 0 3 0 3 3

result:

ok answer = 25

Test #14:

score: 0

Accepted

time: 67ms

memory: 327460kb

input:

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

result:

ok answer = 0

Test #15:

score: 0

Accepted

time: 283ms

memory: 327220kb

input:

output:

0 5 8 0 0 0 0 0 8 5 8 8 5 0 0 0 0 0

result:

ok answer = 60

Test #16:

score: 0

Accepted

time: 199ms

memory: 327292kb

input:

output:

0 0 0 0 5 5 5 0 0 0 0 0 0 0 5 0 5 0

result:

ok answer = 30

Test #17:

score: 0

Accepted

time: 233ms

memory: 327260kb

input:

output:

8 0 0 0 0 0 0 0 0 0 8 0 0 0 7 8 0 7

result:

ok answer = 45

Test #18:

score: 0

Accepted

time: 323ms

memory: 327420kb

input:

output:

2 4 3 4 4 4 4 3 3 3 3 4 0 3 0 3 4 0

result:

ok answer = 90

Test #19:

score: 0

Accepted

time: 204ms

memory: 327180kb

input:

output:

2 2 2 0 2 2 2 3 2 2 0 1 3 0 0 2 2 2

result:

ok answer = 53

Test #20:

score: 0

Accepted

time: 283ms

memory: 327300kb

input:

output:

0 3 3 3 0 3 3 3 3 3 3 3 0 3 3 3 0 3

result:

ok answer = 72

Test #21:

score: 0

Accepted

time: 176ms

memory: 327156kb

input:

output:

0 0 2 2 0 2 2 0 2 2 2 0 2 2 0 0 0 2

result:

ok answer = 38

Test #22:

score: 0

Accepted

time: 382ms

memory: 327220kb

input:

output:

1 0 1 0 8 0 8 0 0 8 8 0 8 0 8 8 8 0

result:

ok answer = 147

Test #23:

score: 0

Accepted

time: 358ms

memory: 327232kb

input:

18 100000 55
8 2
4 15
6 2
4 3
10 15
18 9
10 12
1 6
17 3
18 13
11 5
3 4
17 2
10 5
15 2
15 12
14 9
11 3
10 6
5 7
5 16
10 14
2 12
12 11
4 8
12 5
2 9
11 18
15 14
13 7
18 5
7 16
7 12
17 10
18 14
8 5
9 5
2 13
1 9
14 18
4 2
13 5
7 11
14 15
5 12
2 1
6 13
13 3
12 2
9 1
4 8
17 13
2 17
15 18
4 5
18 10
12 16
14...

output:

4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

result:

ok answer = 300000

Test #24:

score: 0

Accepted

time: 265ms

memory: 327460kb

input:

18 100000 33
4 14
11 2
17 6
10 12
1 12
2 15
17 5
14 18
17 3
10 13
2 8
12 6
12 5
16 15
3 9
5 12
5 9
3 4
9 18
15 1
4 6
8 15
3 11
5 1
11 3
9 3
14 7
3 1
13 16
17 18
18 7
10 1
1 7
11 3
10 16
6 1
7 5
18 2
9 16
12 2
9 14
8 18
7 13
13 8
4 15
16 13
18 11
13 5
2 4
3 12
4 5
2 9
10 14
11 13
13 11
16 1
5 3
15 13...

output:

2 2 2 2 1 2 2 1 2 2 2 2 2 2 2 1 2 2

result:

ok answer = 169113

Test #25:

score: 0

Accepted

time: 477ms

memory: 327232kb

input:

18 100000 79
15 10
2 9
2 1
16 5
17 4
14 16
17 3
16 6
16 1
3 7
17 14
7 15
12 6
12 7
6 15
16 1
11 14
2 6
16 11
14 11
6 3
1 12
5 1
13 9
16 10
15 4
18 11
14 10
16 10
9 16
3 2
10 14
5 6
15 1
17 7
11 7
1 15
16 6
3 8
6 14
16 7
8 17
3 9
3 16
3 6
18 13
8 9
12 14
7 6
14 7
4 14
15 8
2 18
10 6
8 16
17 18
7 1
7 ...

output:

5 4 4 4 4 4 5 4 4 5 4 4 5 4 4 5 5 5

result:

ok answer = 414155

Test #26:

score: 0

Accepted

time: 378ms

memory: 327300kb

input:

18 100000 57
8 7
8 16
3 12
2 16
16 14
7 18
16 17
17 9
15 18
14 16
15 2
1 8
14 6
7 18
11 4
11 8
1 3
15 16
14 13
15 4
6 14
4 12
17 16
5 4
17 15
5 16
17 16
14 5
16 3
13 1
15 5
1 10
12 4
13 18
13 14
5 12
5 16
17 12
14 1
4 15
8 16
4 13
17 2
15 3
10 16
17 3
6 5
12 9
3 9
14 11
13 15
1 2
3 16
1 17
13 15
14 ...

output:

3 3 3 3 3 4 3 3 3 3 3 3 4 3 3 3 4 3

result:

ok answer = 302082

Test #27:

score: 0

Accepted

time: 443ms

memory: 327460kb

input:

18 100000 70
2 3
17 5
6 7
12 7
1 18
16 15
1 15
13 15
7 10
14 7
13 1
13 7
3 10
16 10
6 16
3 5
7 1
16 12
18 17
4 3
15 17
5 6
1 3
12 7
1 13
13 15
17 14
13 10
6 12
14 16
17 2
4 17
13 12
4 17
15 10
9 11
15 18
10 3
12 15
6 9
3 10
9 5
10 1
4 12
11 10
18 1
9 7
2 10
4 12
4 1
11 1
16 11
17 15
2 14
13 11
12 7
...

output:

4 4 4 3 4 3 4 4 4 4 4 4 4 4 4 4 4 4

result:

ok answer = 378879

Test #28:

score: 0

Accepted

time: 171ms

memory: 327132kb

input:

output:

2 2 2 2 2 2 2 2 2 2 0 2 1 0 0 0 0 0

result:

ok answer = 2851

Test #29:

score: 0

Accepted

time: 352ms

memory: 327260kb

input:

output:

4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 0 0 0

result:

ok answer = 7479

Test #30:

score: 0

Accepted

time: 357ms

memory: 327460kb

input:

output:

5 5 5 5 5 4 4 5 4 4 4 4 4 4 4 0 0 0

result:

ok answer = 8450

Test #31:

score: 0

Accepted

time: 484ms

memory: 327196kb

input:

output:

7 7 6 6 6 6 6 6 6 6 6 6 6 6 6 0 0 0

result:

ok answer = 11900

Test #32:

score: 0

Accepted

time: 456ms

memory: 327432kb

input:

output:

6 6 6 6 6 6 6 6 6 6 6 6 6 6 3 0 0 0

result:

ok answer = 11247

Test #33:

score: 0

Accepted

time: 384ms

memory: 327428kb

input:

output:

5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 0 0 0

result:

ok answer = 9000

Test #34:

score: 0

Accepted

time: 372ms

memory: 327392kb

input:

output:

5 5 5 5 5 5 5 4 5 4 4 4 4 4 4 0 0 0

result:

ok answer = 8702

Test #35:

score: 0

Accepted

time: 532ms

memory: 327168kb

input:

18 1950 100
1 2
2 1
2 1
2 1
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1
2 1
1 2
1 2
2 1
2 1
2 1
2 1
1 2
2 1
2 1
2 1
2 1
1 2
1 2
1 2
2 1
2 1
1 2
1 2
2 1
2 1
1 2
2 1
1 2
1 2
2 1
1 2
2 1
2 1
2 1
1 2
1 2
1 2
2 1
1 2
1 2
1 2
2 1
1 2
2 1
2 1
1 2
1 2
2 1
2 1
1 2
1 2
1 2
1 2
1 2
2 1
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1
2 1
...

output:

7 7 7 7 7 7 7 7 7 7 6 6 6 6 6 0 0 0

result:

ok answer = 12900

Test #36:

score: 0

Accepted

time: 5ms

memory: 6748kb

input:

1 0 0

output:

result:

ok answer = 0

Test #37:

score: 0

Accepted

time: 216ms

memory: 327220kb

input:

output:

3 3 3 3 3 3 3 3 3 3 2 1 0 0 0 0 0 0

result:

ok answer = 2855

Test #38:

score: 0

Accepted

time: 532ms

memory: 327168kb

input:

18 1950 100
14 16
4 11
11 9
1 3
18 13
12 3
8 6
7 14
18 6
1 4
7 3
9 16
4 15
15 6
6 11
1 16
7 18
1 14
3 9
11 7
11 3
11 7
8 1
13 3
14 3
12 13
15 2
9 11
9 4
8 6
8 6
1 4
1 12
18 8
11 3
3 13
2 11
18 4
9 11
3 1
8 16
2 18
11 1
12 15
15 11
11 4
9 11
6 12
12 15
7 6
9 4
4 9
13 4
4 9
6 11
4 9
13 4
4 9
9 3
7 1
1...

output:

7 6 7 7 0 7 6 6 7 0 7 7 7 6 7 6 0 7

result:

ok answer = 12900

Test #39:

score: 0

Accepted

time: 265ms

memory: 327236kb

input:

output:

0 1 3 0 0 3 3 2 3 3 3 0 3 0 3 3 0 3

result:

ok answer = 2855

Test #40:

score: 0

Accepted

time: 340ms

memory: 327288kb

input:

output:

3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 1 1 2

result:

ok answer = 4394

Test #41:

score: 0

Accepted

time: 363ms

memory: 327404kb

input:

output:

3 3 3 3 3 3 3 3 3 3 2 3 2 3 1 3 1 3

result:

ok answer = 4392

Test #42:

score: 0

Accepted

time: 380ms

memory: 327200kb

input:

output:

1 3 3 3 3 3 3 1 1 3 3 3 3 3 1 3 3 3

result:

ok answer = 4240

Test #43:

score: 0

Accepted

time: 370ms

memory: 327300kb

input:

output:

3 1 1 3 3 3 3 3 3 3 3 3 1 3 0 3 3 3

result:

ok answer = 4149

Test #44:

score: 0

Accepted

time: 372ms

memory: 327172kb

input:

output:

0 3 3 3 3 3 3 3 3 3 3 0 1 1 3 3 3 3

result:

ok answer = 4052

Test #45:

score: 0

Accepted

time: 393ms

memory: 327460kb

input:

output:

3 0 3 3 3 0 3 1 3 3 0 3 3 3 3 3 3 3

result:

ok answer = 3977

Test #46:

score: 0

Accepted

time: 414ms

memory: 327172kb

input:

output:

3 3 1 3 3 3 3 2 3 3 2 3 3 2 3 3 3 3

result:

ok answer = 4484

Test #47:

score: 0

Accepted

time: 386ms

memory: 327164kb

input:

output:

2 2 3 3 3 3 3 3 3 2 3 3 3 2 3 3 3 3

result:

ok answer = 4580

Test #48:

score: 0

Accepted

time: 424ms

memory: 327268kb

input:

output:

3 3 3 3 3 3 3 3 3 3 3 2 3 3 3 2 2 3

result:

ok answer = 4646

Test #49:

score: 0

Accepted

time: 44ms

memory: 327224kb

input:

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

result:

ok answer = 0

Test #50:

score: 0

Accepted

time: 676ms

memory: 327300kb

input:

18 1640 100
5 16
17 7
17 2
2 16
14 1
15 14
2 17
9 7
16 13
1 2
2 4
14 2
8 1
6 2
14 15
18 12
3 6
7 13
6 11
8 4
1 2
6 10
18 16
15 2
16 6
3 8
10 3
8 6
12 3
8 2
9 16
15 9
14 8
2 17
14 9
4 14
2 13
17 7
10 5
16 17
17 1
4 2
7 14
15 13
13 18
11 13
4 8
5 3
18 9
11 15
1 4
17 9
16 6
10 5
10 3
15 7
7 13
18 5
9 1...

output:

7 7 1 7 0 7 7 7 7 1 7 0 7 7 7 7 7 7

result:

ok answer = 9253