QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#456754#3221. Clique ColoringpropaneAC ✓1ms3864kbC++201.6kb2024-06-28 12:11:322024-06-28 12:11:33

Judging History

This is the latest submission verdict.

  • [2024-06-28 12:11:33]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3864kb
Show
  • [2024-06-28 12:11:32]
  • Submitted

answer

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin >> n;
    vector<LL> a(n);
    LL sum = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        sum += a[i];
    }
    int mx = 0;

    vector<int> p;
    for(int i = 0; i < 1 << n; i++){
        if (__builtin_popcount(i) > 1){
            p.push_back(i);
        }
    }

    vector<int> v;

    auto dfs = [&](auto &&dfs, int u) -> void {
        if (u == p.size()){
            int cnt = 0;
            vector<int> c(n);
            for(auto x : v){
                for(int i = 0; i < n; i++){
                    if (x >> i & 1){
                        c[i] += 1;
                    }
                }
                cnt += __builtin_popcount(x) - 1;
            }
            bool ok = true;
            for(int i = 0; i < n; i++){
                if (c[i] > a[i]){
                    ok = false;
                    break;
                }
            }
            if (ok) mx = max(mx, cnt);
            return;
        }
        dfs(dfs, u + 1);
        bool ok = true;
        for(auto x : v){
            if (__builtin_popcount(x & p[u]) > 1){
                ok = false;
                break;
            }
        }
        if (ok){
            v.push_back(p[u]);
            dfs(dfs, u + 1);
            v.pop_back();
        }
    };

    dfs(dfs, 0);
    cout << sum - mx << '\n';

}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
4

output:

4

result:

ok single line: '4'

Test #2:

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

input:

2
4
1000000000

output:

1000000003

result:

ok single line: '1000000003'

Test #3:

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

input:

3
447893992
4
1000000000

output:

1447893993

result:

ok single line: '1447893993'

Test #4:

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

input:

4
1000000000
1000000000
409299805
305205736

output:

2714505535

result:

ok single line: '2714505535'

Test #5:

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

input:

5
701636407
83399801
260677870
1000000000
4

output:

2045714072

result:

ok single line: '2045714072'

Test #6:

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

input:

1
3

output:

3

result:

ok single line: '3'

Test #7:

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

input:

2
497280904
3

output:

497280906

result:

ok single line: '497280906'

Test #8:

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

input:

3
3
4
495505982

output:

495505986

result:

ok single line: '495505986'

Test #9:

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

input:

4
4
3
4
4

output:

9

result:

ok single line: '9'

Test #10:

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

input:

5
4
4
3
4
1000000000

output:

1000000006

result:

ok single line: '1000000006'

Test #11:

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

input:

2
3
3

output:

5

result:

ok single line: '5'

Test #12:

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

input:

3
1000000000
3
3

output:

1000000003

result:

ok single line: '1000000003'

Test #13:

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

input:

4
378634918
3
3
4

output:

378634922

result:

ok single line: '378634922'

Test #14:

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

input:

5
693604254
3
3
1000000000
4

output:

1693604255

result:

ok single line: '1693604255'

Test #15:

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

input:

3
3
3
3

output:

6

result:

ok single line: '6'

Test #16:

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

input:

4
3
3
741443949
3

output:

741443952

result:

ok single line: '741443952'

Test #17:

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

input:

5
798458902
3
3
85709420
3

output:

884168322

result:

ok single line: '884168322'

Test #18:

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

input:

4
3
3
3
3

output:

6

result:

ok single line: '6'

Test #19:

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

input:

5
3
3
4
3
3

output:

8

result:

ok single line: '8'

Test #20:

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

input:

5
3
3
3
3
3

output:

7

result:

ok single line: '7'

Test #21:

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

input:

1
2

output:

2

result:

ok single line: '2'

Test #22:

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

input:

2
1000000000
2

output:

1000000001

result:

ok single line: '1000000001'

Test #23:

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

input:

3
275630553
2
1000000000

output:

1275630552

result:

ok single line: '1275630552'

Test #24:

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

input:

4
4
85561698
2
4

output:

85561703

result:

ok single line: '85561703'

Test #25:

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

input:

5
343830664
2
266706206
477214206
4

output:

1087751074

result:

ok single line: '1087751074'

Test #26:

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

input:

2
2
3

output:

4

result:

ok single line: '4'

Test #27:

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

input:

3
2
3
1000000000

output:

1000000002

result:

ok single line: '1000000002'

Test #28:

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

input:

4
3
2
277873868
1000000000

output:

1277873868

result:

ok single line: '1277873868'

Test #29:

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

input:

5
2
136812254
473248215
3
4

output:

610060470

result:

ok single line: '610060470'

Test #30:

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

input:

3
3
2
3

output:

5

result:

ok single line: '5'

Test #31:

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

input:

4
3
2
1000000000
3

output:

1000000003

result:

ok single line: '1000000003'

Test #32:

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

input:

5
2
3
261722051
3
1000000000

output:

1261722051

result:

ok single line: '1261722051'

Test #33:

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

input:

4
3
3
3
2

output:

6

result:

ok single line: '6'

Test #34:

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

input:

5
3
3
857509551
3
2

output:

857509554

result:

ok single line: '857509554'

Test #35:

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

input:

5
3
3
3
2
3

output:

6

result:

ok single line: '6'

Test #36:

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

input:

2
2
2

output:

3

result:

ok single line: '3'

Test #37:

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

input:

3
2
1000000000
2

output:

1000000001

result:

ok single line: '1000000001'

Test #38:

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

input:

4
615064899
2
2
4

output:

615064902

result:

ok single line: '615064902'

Test #39:

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

input:

5
4
1000000000
1000000000
2
2

output:

2000000001

result:

ok single line: '2000000001'

Test #40:

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

input:

3
2
3
2

output:

4

result:

ok single line: '4'

Test #41:

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

input:

4
4
2
3
2

output:

6

result:

ok single line: '6'

Test #42:

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

input:

5
2
3
1000000000
4
2

output:

1000000004

result:

ok single line: '1000000004'

Test #43:

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

input:

4
2
3
2
3

output:

5

result:

ok single line: '5'

Test #44:

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

input:

5
2
3
54069329
2
3

output:

54069332

result:

ok single line: '54069332'

Test #45:

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

input:

5
3
3
3
2
2

output:

6

result:

ok single line: '6'

Test #46:

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

input:

3
2
2
2

output:

3

result:

ok single line: '3'

Test #47:

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

input:

4
2
4
2
2

output:

5

result:

ok single line: '5'

Test #48:

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

input:

5
2
2
395669578
2
906198920

output:

1301868497

result:

ok single line: '1301868497'

Test #49:

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

input:

4
3
2
2
2

output:

4

result:

ok single line: '4'

Test #50:

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

input:

5
3
2
1000000000
2
2

output:

1000000002

result:

ok single line: '1000000002'

Test #51:

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

input:

5
2
3
2
3
2

output:

5

result:

ok single line: '5'

Test #52:

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

input:

4
2
2
2
2

output:

4

result:

ok single line: '4'

Test #53:

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

input:

5
2
2
2
1000000000
2

output:

1000000001

result:

ok single line: '1000000001'

Test #54:

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

input:

5
2
2
2
3
2

output:

5

result:

ok single line: '5'

Test #55:

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

input:

5
2
2
2
2
2

output:

4

result:

ok single line: '4'

Test #56:

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

input:

5
1000000000
1000000000
1000000000
1000000000
1000000000

output:

4999999990

result:

ok single line: '4999999990'

Test #57:

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

input:

2
3
3

output:

5

result:

ok single line: '5'

Test #58:

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

input:

5
2
3
4
5
6

output:

12

result:

ok single line: '12'
English 繁體中文 简体中文

Server Time: 2025-04-12 10:00:49 | OpenSource Project