QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#323940#4829. Mark on a Graphhotboy27030 2ms4080kbC++142.5kb2024-02-10 14:28:122024-02-10 14:28:12

Judging History

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

  • [2024-02-10 14:28:12]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:4080kb
  • [2024-02-10 14:28:12]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
ll n,m;
vector <ll> g[1010];
const ll check = 100;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    vector <pll> edge;
    for (ll i = 1;i <= m;i ++){
        ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        edge.push_back({u,v});
    }
    ll cnt[check]={};
    for (ll i = 1;i <= n;i ++){
        if (sz(g[i])<check)cnt[sz(g[i])]^=1;
    }
    ll sum = 0;
    for (ll i = 0;i < check;i ++)sum += cnt[i];
    if (sum>3){
        cout<<"mark\n";
        vector <pll> del;
        for (ll i = 0;i < 5;i ++){
            ll best = sum;
            pll nw = {0,0};
            for (ll j = 1;j <= n;j ++){
                for (auto x:g[j]){
                    vector <ll> dif({sz(g[j]),sz(g[j])-1,sz(g[x]),sz(g[x])-1});
                    for (auto y:dif){
                        sum -= cnt[y];
                        cnt[y]^=1;
                        sum += cnt[y];
                    }
                    if (sum < best){
                        best = sum;
                        nw = {j,x};
                    }
                    for (auto y:dif){
                        sum -= cnt[y];
                        cnt[y]^=1;
                        sum += cnt[y];
                    }
                }
            }
            if (nw.fi != 0){
                ll j,x;
                j = nw.fi,x=nw.se;
                del.push_back({j,x});
                vector <ll> dif({sz(g[j]),sz(g[j])-1,sz(g[x]),sz(g[x])-1});
                for (auto y:dif){
                    sum -= cnt[y];
                    cnt[y]^=1;
                    sum += cnt[y];
                }
                for (ll k = 0;k < sz(g[j]);k++){
                    if (g[j][k]==x){
                        g[j].erase(g[j].begin()+k);
                    }
                }
                for (ll k = 0;k < sz(g[x]);k++){
                    if (g[x][k]==j){
                        g[x].erase(g[x].begin()+k);
                    }
                }

            }
        }
        cout<<sz(del)<<'\n';
        for (auto x:del)cout<<x.fi<<' '<<x.se<<'\n';
    }
    else{
        cout<<"ok";
    }
//    cout<<even<<'\n';
}


详细

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 4080kb

input:

1000 3560
603 151
415 20
102 569
895 552
678 734
24 614
689 518
440 223
751 919
223 433
711 551
502 634
706 583
812 501
514 535
780 751
720 530
532 384
888 139
864 791
292 675
171 881
30 592
464 557
280 299
654 650
894 335
250 532
792 10
83 969
118 771
579 300
852 983
243 940
957 939
817 889
911 319...

output:

mark
2
10 792
50 611

input:

1000 3558
397 554
396 217
262 376
854 911
576 186
50 833
648 137
232 739
184 286
383 34
83 863
355 48
930 18
167 755
283 323
250 209
722 567
667 500
215 595
253 49
479 363
51 964
263 292
831 175
375 735
125 692
102 654
437 827
125 457
932 719
551 339
353 721
379 167
163 430
272 547
620 759
360 898
5...

output:

mark
0

result:

wrong answer Token "mark" doesn't correspond to pattern "ok"