QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#324018	#4829. Mark on a Graph	hotboy2703	AC ✓	620ms	12368kb	C++14	2.0kb	2024-02-10 15:14:08	2024-02-10 15:14:09

Judging History

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

[2024-02-10 15:14:09]
评测

测评结果：AC
用时：620ms
内存：12368kb

查看

[2024-02-10 15:14:08]
提交

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))
mt19937_64 rng(1);
ll random(ll l,ll r){
    return rng()%(r-l+1)+l;
}
ll myrandom(ll i){
    return rng()%i;
}
ll n,m;
ll val[1010][1010];
struct graph{
    set <pll> s;
    void add_edge(ll u,ll v){
        if (u > v)swap(u,v);
        if (s.find({u,v})==s.end())s.insert({u,v});
        else s.erase({u,v});
    }
    ll cnt[1010];
    ll eval(){
        memset(cnt,0,sizeof cnt);
        for (auto x:s)cnt[x.fi]++,cnt[x.se]++;
        ll res = 0;
        for (auto x:s){
            if (cnt[x.fi]<cnt[x.se])swap(x.fi,x.se);
            res ^= val[cnt[x.fi]][cnt[x.se]];
        }
        return res;
    }
};
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    for (ll i = 1;i <= 1000;i ++){
        for (ll j = 1;j <= 1000;j ++){
            val[i][j] = random(0,1023);
        }
    }
    cin>>n>>m;
    graph g;
    for (ll i = 1;i <= m;i ++){
        ll u,v;
        cin>>u>>v;
        g.add_edge(u,v);
    }
    if (g.eval() == 69){
        cout<<"ok"<<endl;
    }
    else{
        cout<<"mark"<<endl;
        vector <pll> ans;
        while (1){
            vector <pll> cur;

            for (ll i = 0;i < 5;i++){
                ll u,v;
                u = random(1,n),v = random(1,n);
                while (u==v)u = random(1,n),v = random(1,n);
                cur.push_back({u,v});
            }
            graph tmp = g;
            for (auto x:cur){
                tmp.add_edge(x.fi,x.se);
            }
            if (tmp.eval()==69){
                ans = cur;
                break;
            }
        }
        cout<<sz(ans)<<'\n';
        for (auto x:ans)cout<<x.fi<<' '<<x.se<<'\n';;
    }
//    cout<<even<<'\n';
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 518ms

memory: 11960kb

input:

output:

input:

output:

ok

result:

ok all right

Test #2:

score: 100

Accepted

time: 32ms

memory: 11912kb

input:

output:

input:

output:

ok

result:

ok all right

Test #3:

score: 100

Accepted

time: 103ms

memory: 12368kb

input:

output:

input:

output:

ok

result:

ok all right

Test #4:

score: 100

Accepted

time: 201ms

memory: 12080kb

input:

output:

input:

output:

ok

result:

ok all right

Test #5:

score: 100

Accepted

time: 76ms

memory: 11936kb

input:

output:

input:

output:

ok

result:

ok all right

Test #6:

score: 100

Accepted

time: 136ms

memory: 11908kb

input:

output:

input:

output:

ok

result:

ok all right

Test #7:

score: 100

Accepted

time: 19ms

memory: 12112kb

input:

output:

input:

output:

ok

result:

ok all right

Test #8:

score: 100

Accepted

time: 266ms

memory: 12008kb

input:

output:

input:

output:

ok

result:

ok all right

Test #9:

score: 100

Accepted

time: 245ms

memory: 12048kb

input:

output:

input:

output:

ok

result:

ok all right

Test #10:

score: 100

Accepted

time: 620ms

memory: 11972kb

input:

output:

input:

output:

ok

result:

ok all right

Test #11:

score: 100

Accepted

time: 31ms

memory: 11956kb

input:

output:

input:

output:

ok

result:

ok all right

Test #12:

score: 100

Accepted

time: 614ms

memory: 12164kb

input:

output:

input:

output:

ok

result:

ok all right

Test #13:

score: 100

Accepted

time: 67ms

memory: 11856kb

input:

output:

input:

output:

ok

result:

ok all right

Test #14:

score: 100

Accepted

time: 139ms

memory: 12032kb

input:

output:

input:

output:

ok

result:

ok all right

Test #15:

score: 100

Accepted

time: 185ms

memory: 11796kb

input:

output:

input:

output:

ok

result:

ok all right

Test #16:

score: 100

Accepted

time: 192ms

memory: 11812kb

input:

output:

input:

output:

ok

result:

ok all right

Test #17:

score: 100

Accepted

time: 99ms

memory: 11848kb

input:

output:

input:

output:

ok

result:

ok all right

Test #18:

score: 100

Accepted

time: 48ms

memory: 12136kb

input:

output:

input:

output:

ok

result:

ok all right

Test #19:

score: 100

Accepted

time: 615ms

memory: 11940kb

input:

output:

input:

output:

ok

result:

ok all right

Test #20:

score: 100

Accepted

time: 293ms

memory: 12268kb

input:

output:

input:

output:

ok

result:

ok all right

Test #21:

score: 100

Accepted

time: 223ms

memory: 11940kb

input:

output:

input:

output:

ok

result:

ok all right

Test #22:

score: 100

Accepted

time: 42ms

memory: 11940kb

input:

output:

input:

output:

ok

result:

ok all right

Test #23:

score: 100

Accepted

time: 69ms

memory: 11948kb

input:

output:

input:

output:

ok

result:

ok all right

Test #24:

score: 100

Accepted

time: 9ms

memory: 11808kb

input:

output:

input:

output:

ok

result:

ok all right

Test #25:

score: 100

Accepted

time: 87ms

memory: 11972kb

input:

output:

input:

output:

ok

result:

ok all right

Test #26:

score: 100

Accepted

time: 262ms

memory: 11940kb

input:

output:

input:

output:

ok

result:

ok all right

Test #27:

score: 100

Accepted

time: 220ms

memory: 11880kb

input:

output:

input:

output:

ok

result:

ok all right

Test #28:

score: 100

Accepted

time: 131ms

memory: 12032kb

input:

output:

input:

output:

ok

result:

ok all right

Test #29:

score: 100

Accepted

time: 557ms

memory: 12132kb

input:

output:

input:

output:

ok

result:

ok all right

Test #30:

score: 100

Accepted

time: 613ms

memory: 12040kb

input:

output:

input:

output:

ok

result:

ok all right

Test #31:

score: 100

Accepted

time: 310ms

memory: 11884kb

input:

output:

input:

output:

ok

result:

ok all right

Test #32:

score: 100

Accepted

time: 193ms

memory: 12172kb

input:

output:

input:

output:

ok

result:

ok all right

Test #33:

score: 100

Accepted

time: 238ms

memory: 12272kb

input:

output:

input:

output:

ok

result:

ok all right

Test #34:

score: 100

Accepted

time: 21ms

memory: 11944kb

input:

output:

input:

output:

ok

result:

ok all right

Test #35:

score: 100

Accepted

time: 37ms

memory: 11796kb

input:

output:

input:

output:

ok

result:

ok all right

Test #36:

score: 100

Accepted

time: 32ms

memory: 11780kb

input:

output:

input:

output:

ok

result:

ok all right

Test #37:

score: 100

Accepted

time: 35ms

memory: 11796kb

input:

output:

input:

output:

ok

result:

ok all right

Test #38:

score: 100

Accepted

time: 41ms

memory: 11928kb

input:

output:

input:

output:

ok

result:

ok all right

Test #39:

score: 100

Accepted

time: 40ms

memory: 11716kb

input:

output:

input:

output:

ok

result:

ok all right

Test #40:

score: 100

Accepted

time: 55ms

memory: 11988kb

input:

output:

input:

output:

ok

result:

ok all right

Test #41:

score: 100

Accepted

time: 58ms

memory: 11760kb

input:

output:

input:

output:

ok

result:

ok all right

Test #42:

score: 100

Accepted

time: 84ms

memory: 11984kb

input:

output:

input:

output:

ok

result:

ok all right

Test #43:

score: 100

Accepted

time: 98ms

memory: 11820kb

input:

output:

input:

output:

ok

result:

ok all right

Test #44:

score: 100

Accepted

time: 31ms

memory: 11692kb

input:

output:

input:

output:

ok

result:

ok all right

Test #45:

score: 100

Accepted

time: 29ms

memory: 11788kb

input:

output:

input:

output:

ok

result:

ok all right

Test #46:

score: 100

Accepted

time: 116ms

memory: 11772kb

input:

output:

input:

output:

ok

result:

ok all right

Test #47:

score: 100

Accepted

time: 168ms

memory: 11800kb

input:

output:

input:

output:

ok

result:

ok all right

Test #48:

score: 100

Accepted

time: 92ms

memory: 11704kb

input:

output:

input:

output:

ok

result:

ok all right

Test #49:

score: 100

Accepted

time: 263ms

memory: 12360kb

input:

output:

input:

output:

ok

result:

ok all right

Test #50:

score: 100

Accepted

time: 45ms

memory: 12132kb

input:

output:

input:

output:

ok

result:

ok all right

Test #51:

score: 100

Accepted

time: 91ms

memory: 12156kb

input:

output:

input:

output:

ok

result:

ok all right

Test #52:

score: 100

Accepted

time: 45ms

memory: 12128kb

input:

output:

input:

output:

ok

result:

ok all right

Test #53:

score: 100

Accepted

time: 24ms

memory: 12364kb

input:

output:

input:

output:

ok

result:

ok all right

Test #54:

score: 100

Accepted

time: 109ms

memory: 12064kb

input:

output:

input:

output:

ok

result:

ok all right

Test #55:

score: 100

Accepted

time: 70ms

memory: 12348kb

input:

output:

input:

output:

ok

result:

ok all right

Test #56:

score: 100

Accepted

time: 320ms

memory: 12304kb

input:

output:

input:

output:

ok

result:

ok all right

Test #57:

score: 100

Accepted

time: 121ms

memory: 12136kb

input:

output:

input:

output:

ok

result:

ok all right

Test #58:

score: 100

Accepted

time: 174ms

memory: 12280kb

input:

output:

input:

output:

ok

result:

ok all right

Test #59:

score: 100

Accepted

time: 289ms

memory: 12036kb

input:

output:

input:

output:

ok

result:

ok all right

Test #60:

score: 100

Accepted

time: 432ms

memory: 12356kb

input:

output:

input:

output:

ok

result:

ok all right

Test #61:

score: 100

Accepted

time: 248ms

memory: 12280kb

input:

output:

input:

output:

ok

result:

ok all right

Test #62:

score: 100

Accepted

time: 19ms

memory: 12144kb

input:

output:

input:

output:

ok

result:

ok all right

Test #63:

score: 100

Accepted

time: 108ms

memory: 12148kb

input:

output:

input:

output:

ok

result:

ok all right