QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#294615 | #4829. Mark on a Graph | ucup-team112# | 0 | 2ms | 4212kb | C++20 | 12.6kb | 2023-12-30 15:00:56 | 2023-12-30 15:00:57 |
answer
//#define _GLIBCXX_DEBUG
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug_print.hpp>
#define OUT(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define OUT(...) (static_cast<void>(0))
#endif
#define endl '\n'
#define lfs cout<<fixed<<setprecision(15)
#define ALL(a) (a).begin(),(a).end()
#define ALLR(a) (a).rbegin(),(a).rend()
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD1 = 1e9+7;
const ll MOD9 = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T> using PQ = priority_queue<T>;
template<typename T> using QP = priority_queue<T,vector<T>,greater<T>>;
template<typename T1, typename T2>bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
template<typename T1, typename T2>bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}
template<typename T1,typename T2,typename T3>void anss(T1 x,T2 y,T3 z){ans(x!=y,x,z);};
template<typename T>void debug(const T &v,ll h,ll w,string sv=" "){for(ll i=0;i<h;i++){cout<<v[i][0];for(ll j=1;j<w;j++)cout<<sv<<v[i][j];cout<<endl;}};
template<typename T>void debug(const T &v,ll n,string sv=" "){if(n!=0)cout<<v[0];for(ll i=1;i<n;i++)cout<<sv<<v[i];cout<<endl;};
template<typename T>void debug(const vector<T>&v){debug(v,v.size());}
template<typename T>void debug(const vector<vector<T>>&v){for(auto &vv:v)debug(vv,vv.size());}
template<typename T>void debug(stack<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
template<typename T>void debug(queue<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop();}cout<<endl;}
template<typename T>void debug(deque<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop_front();}cout<<endl;}
template<typename T>void debug(PQ<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
template<typename T>void debug(QP<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
template<typename T>void debug(const set<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
template<typename T>void debug(const multiset<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
template<typename T,size_t size>void debug(const array<T, size> &a){for(auto z:a)cout<<z<<" ";cout<<endl;}
template<typename T,typename V>void debug(const map<T,V>&v){for(auto z:v)cout<<"["<<z.first<<"]="<<z.second<<",";cout<<endl;}
template<typename T>vector<vector<T>>vec(ll x, ll y, T w){vector<vector<T>>v(x,vector<T>(y,w));return v;}
vector<ll>dx={1,-1,0,0,1,1,-1,-1};vector<ll>dy={0,0,1,-1,1,-1,1,-1};
template<typename T>vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}
template<typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2>&p){return os << "(" << p.first << "," << p.second << ")";}
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v){os<<"[";for(auto &z:v)os << z << ",";os<<"]"; return os;}
template<typename T>void rearrange(vector<int>&ord, vector<T>&v){
auto tmp = v;
for(int i=0;i<tmp.size();i++)v[i] = tmp[ord[i]];
}
template<typename Head, typename... Tail>void rearrange(vector<int>&ord,Head&& head, Tail&&... tail){
rearrange(ord, head);
rearrange(ord, tail...);
}
template<typename T> vector<int> ascend(const vector<T>&v){
vector<int>ord(v.size());iota(ord.begin(),ord.end(),0);
sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],i)<make_pair(v[j],j);});
return ord;
}
template<typename T> vector<int> descend(const vector<T>&v){
vector<int>ord(v.size());iota(ord.begin(),ord.end(),0);
sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],-i)>make_pair(v[j],-j);});
return ord;
}
template<typename T> vector<T> inv_perm(const vector<T>&ord){
vector<T>inv(ord.size());
for(int i=0;i<ord.size();i++)inv[ord[i]] = i;
return inv;
}
ll FLOOR(ll n,ll div){assert(div>0);return n>=0?n/div:(n-div+1)/div;}
ll CEIL(ll n,ll div){assert(div>0);return n>=0?(n+div-1)/div:n/div;}
ll digitsum(ll n){ll ret=0;while(n){ret+=n%10;n/=10;}return ret;}
ll modulo(ll n,ll d){return (n%d+d)%d;};
template<typename T>T min(const vector<T>&v){return *min_element(v.begin(),v.end());}
template<typename T>T max(const vector<T>&v){return *max_element(v.begin(),v.end());}
template<typename T>T acc(const vector<T>&v){return accumulate(v.begin(),v.end(),T(0));};
template<typename T>T reverse(const T &v){return T(v.rbegin(),v.rend());};
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int popcount(ll x){return __builtin_popcountll(x);};
int poplow(ll x){return __builtin_ctzll(x);};
int pophigh(ll x){return 63 - __builtin_clzll(x);};
template<typename T>T poll(queue<T> &q){auto ret=q.front();q.pop();return ret;};
template<typename T>T poll(priority_queue<T> &q){auto ret=q.top();q.pop();return ret;};
template<typename T>T poll(QP<T> &q){auto ret=q.top();q.pop();return ret;};
template<typename T>T poll(stack<T> &s){auto ret=s.top();s.pop();return ret;};
ll MULT(ll x,ll y){if(LLONG_MAX/x<=y)return LLONG_MAX;return x*y;}
ll POW2(ll x, ll k){ll ret=1,mul=x;while(k){if(mul==LLONG_MAX)return LLONG_MAX;if(k&1)ret=MULT(ret,mul);mul=MULT(mul,mul);k>>=1;}return ret;}
ll POW(ll x, ll k){ll ret=1;for(int i=0;i<k;i++){if(LLONG_MAX/x<=ret)return LLONG_MAX;ret*=x;}return ret;}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
std::ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = std::end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = std::end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}
namespace converter{
int dict[500];
const string lower="abcdefghijklmnopqrstuvwxyz";
const string upper="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string digit="0123456789";
const string digit1="123456789";
void regi_str(const string &t){
for(int i=0;i<t.size();i++){
dict[t[i]]=i;
}
}
void regi_int(const string &t){
for(int i=0;i<t.size();i++){
dict[i]=t[i];
}
}
vector<int>to_int(const string &s,const string &t){
regi_str(t);
vector<int>ret(s.size());
for(int i=0;i<s.size();i++){
ret[i]=dict[s[i]];
}
return ret;
}
vector<int>to_int(const string &s){
auto t=s;
sort(t.begin(),t.end());
t.erase(unique(t.begin(),t.end()),t.end());
return to_int(s,t);
}
vector<vector<int>>to_int(const vector<string>&s,const string &t){
regi_str(t);
vector<vector<int>>ret(s.size(),vector<int>(s[0].size()));
for(int i=0;i<s.size();i++){
for(int j=0;j<s[0].size();j++){
ret[i][j]=dict[s[i][j]];
}
}
return ret;
}
vector<vector<int>>to_int(const vector<string>&s){
string t;
for(int i=0;i<s.size();i++){
t+=s[i];
}
sort(t.begin(),t.end());t.erase(unique(t.begin(),t.end()),t.end());
return to_int(s,t);
}
string to_str(const vector<int>&s,const string &t){
regi_int(t);
string ret;
for(auto z:s)ret+=dict[z];
return ret;
}
vector<string> to_str(const vector<vector<int>>&s,const string &t){
regi_int(t);
vector<string>ret(s.size());
for(int i=0;i<s.size();i++){
for(auto z:s[i])ret[i]+=dict[z];
}
return ret;
}
}
template< typename T = int >
struct edge {
int to;
T cost;
int id;
edge():to(-1),id(-1){};
edge(int to, T cost = 1, int id = -1):to(to), cost(cost), id(id){}
operator int() const { return to; }
};
template<typename T>
using Graph = vector<vector<edge<T>>>;
template<typename T>
Graph<T>revgraph(const Graph<T> &g){
Graph<T>ret(g.size());
for(int i=0;i<g.size();i++){
for(auto e:g[i]){
int to = e.to;
e.to = i;
ret[to].push_back(e);
}
}
return ret;
}
template<typename T>
Graph<T> readGraph(int n,int m,int indexed=1,bool directed=false,bool weighted=false){
Graph<T> ret(n);
for(int es = 0; es < m; es++){
int u,v;
T w=1;
cin>>u>>v;u-=indexed,v-=indexed;
if(weighted)cin>>w;
ret[u].emplace_back(v,w,es);
if(!directed)ret[v].emplace_back(u,w,es);
}
return ret;
}
template<typename T>
Graph<T> readParent(int n,int indexed=1,bool directed=true){
Graph<T>ret(n);
for(int i=1;i<n;i++){
int p;cin>>p;
p-=indexed;
ret[p].emplace_back(i);
if(!directed)ret[i].emplace_back(p);
}
return ret;
}
struct RandomNumberGenerator {
mt19937_64 mt;
RandomNumberGenerator() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}
RandomNumberGenerator(int x) : mt(x){
cout<<"-----debug-----"<<endl;
}
ll operator()(ll a, ll b) { // [a, b)
uniform_int_distribution< ll > dist(a, b - 1);
return dist(mt);
}
ll operator()(ll b) { // [0, b)
return (*this)(0, b);
}
};
RandomNumberGenerator rng;
Graph<int>gen(ll n,ll m){
set<pair<int,int>>st;
Graph<int>g(n);
while(m--){
while(1){
ll u=rng(0,n);
ll v=rng(0,n);
if(u==v)continue;
if(st.count(minmax(u,v)))continue;
g[u].EB(v);
g[v].EB(u);
st.insert(minmax(u,v));
break;
}
}
return g;
}
struct UnionFind {
vector<ll> data;
ll num;
UnionFind(ll size) : data(size, -1) ,num(size){ }
bool unite(int x, int y) {
x = root(x); y = root(y);
if (x != y) {
if (data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
num--;
}
return x != y;
}
bool find(int x, int y) {
return root(x) == root(y);
}
int root(int x) {
return data[x] < 0 ? x : data[x] = root(data[x]);
}
ll size(int x) {
return -data[root(x)];
}
vector<vector<int>>groups(){
vector<vector<int>>ret(data.size());
for(int i=0;i<data.size();i++){
ret[root(i)].push_back(i);
}
return ret;
}
void print(){
auto tmp=groups();
for(int i=0;i<data.size();i++){
if(!tmp[i].empty()){
for(auto z:tmp[i])cout<<z<<",";
cout<<endl;
}
}
}
};
vector<int> check_clique(Graph<int>g){
int n=g.size();
vector<vector<int>>adj(n);
rep(i,0,n){
for(auto to:g[i])if(i<to)adj[i].PB(to);
sort(ALL(adj[i]));
}
ll mx=0;
vector<int>rcv;
rep(i,0,n){
vector<int>p;
auto dfs=[&](auto &&f,int v)->void {
p.PB(v);
if(chmax(mx,p.size()))rcv=p;
for(auto to:adj[v]){
bool sw=true;
for(auto z:p){
if(z!=v&&!binary_search(ALL(adj[z]),v)){
sw=false;
break;
}
}
if(!sw)break;
f(f,to);
}
p.pop_back();
};
dfs(dfs,i);
}
return rcv;
}
int main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
ll res=0,buf=0;
bool judge = true;
map<ll,ll>mp;
// rep(_,0,1000){
// ll n=1000;
// auto g=gen(n,rng(2000,5001));
int n,m;cin>>n>>m;
auto g=readGraph<int>(n,m);
//auto g=gen(n,m);
// UnionFind uf(n);
// rep(i,0,n){
// for(auto to:g[i])uf.unite(i,to);
// }
auto rp=check_clique(g);
if(rp.size()==4){
vector<vector<int>>adj(n);
rep(i,0,n){
for(auto to:g[i])adj[i].PB(to);
sort(ALL(adj[i]));
}
set<int>st(ALL(rp));
cout<<"mark"<<endl;
vector<P>ret;
rep(i,0,n){
if(!st.count(i)){
for(auto to:st){
if(!binary_search(ALL(adj[to]),i)){
ret.EB(i,to);
//g[to].EB(i);
//g[i].EB(to);
}
}
break;
}
}
cout<<ret.size()<<endl;
for(auto z:ret)cout<<z.fi+1 spa z.se+1<<endl;
}
else cout<<"ok"<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4212kb
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 4 1 7 1 417 1 643 1 669
input:
1000 3564 652 669 821 396 536 662 865 475 726 163 833 495 681 118 781 363 189 184 392 102 831 639 48 932 510 807 180 790 332 494 640 763 66 4 850 500 126 422 932 784 368 691 958 387 292 227 583 66 999 937 125 726 351 806 777 437 728 375 924 747 339 423 121 721 790 314 267 511 201 790 18 186 937 761 ...
output:
ok
result:
ok all right
Test #2:
score: 100
Accepted
time: 1ms
memory: 4116kb
input:
1000 2000 457 335 160 497 464 992 892 255 853 3 308 301 970 363 541 299 89 418 425 128 626 827 603 854 484 874 755 295 607 483 798 552 356 850 320 357 254 940 675 901 168 525 301 636 520 555 773 910 343 701 889 966 218 529 909 950 71 64 682 284 424 138 721 792 670 544 386 72 654 909 725 235 592 437 ...
output:
mark 4 1 27 1 133 1 368 1 567
input:
1000 2004 911 552 132 971 118 519 250 778 65 819 148 722 351 365 594 433 253 657 431 764 505 764 130 848 295 489 510 650 332 848 169 283 322 871 36 153 363 522 419 602 809 444 616 236 489 670 465 193 999 663 906 484 271 858 246 835 660 3 58 21 685 13 411 674 23 666 569 980 670 270 164 502 633 94 303...
output:
ok
result:
ok all right
Test #3:
score: 100
Accepted
time: 2ms
memory: 4076kb
input:
1000 5000 449 632 597 26 701 322 249 190 411 770 666 596 989 995 112 861 445 818 544 659 24 680 739 593 344 439 193 932 600 526 574 869 216 918 716 793 259 686 555 993 255 578 659 271 328 524 729 672 39 771 241 866 27 790 417 109 56 403 338 299 387 232 280 306 589 794 833 419 900 802 54 697 539 807 ...
output:
mark 4 2 1 2 308 2 507 2 607
input:
1000 5004 258 506 885 742 458 536 208 588 918 845 699 782 361 150 350 986 809 920 157 914 578 699 634 106 213 405 639 570 83 610 647 685 128 762 345 596 821 596 976 32 564 332 60 376 552 471 116 819 847 792 399 48 98 104 771 301 726 21 138 143 612 419 42 15 693 177 272 533 766 697 17 612 105 530 240...
output:
ok
result:
ok all right
Test #4:
score: 0
Wrong Answer
time: 1ms
memory: 3964kb
input:
1000 3156 347 398 792 278 754 442 413 757 391 130 636 625 207 437 81 415 47 974 887 779 524 619 379 894 868 594 653 919 29 117 123 867 632 505 648 147 130 420 495 876 637 659 882 348 462 878 282 646 398 525 419 224 926 448 305 934 855 570 396 345 774 918 336 123 502 491 984 783 845 142 790 594 754 4...
output:
mark 4 1 6 1 579 1 727 1 957
input:
1000 3160 540 769 372 439 654 904 845 585 753 154 533 297 215 177 475 825 399 266 439 852 556 16 487 971 843 648 150 509 841 721 611 811 355 642 492 1000 959 437 38 885 350 865 20 309 885 399 287 297 253 812 357 456 28 157 766 794 353 918 668 290 18 225 811 609 426 394 127 255 836 338 216 517 334 74...
output:
mark 4 1 5 1 184 1 231 1 280
result:
wrong answer Token "mark" doesn't correspond to pattern "ok"