Submission #4074881


Source Code Expand

#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
#define fi first
#define se second

unsigned long long xor128() {
    static unsigned long long rx = 123456789, ry = 362436069, rz = 521288629, rw = 88675123;
    unsigned long long rt = (rx ^ (rx << 11));
    rx = ry;
    ry = rz;
    rz = rw;
    return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8)));
}


int n,m;
vector<int>v[44];



int max_ind(){
  int a[n],ans=0,used[n];
  r(i,n)a[i]=i;
  for(int o=0;o<1000000;o++){
    memset(used,0,sizeof(used));
    int sum=0;
    r(i,n){
      int f=0;
      r(j,v[a[i]].size()){
        if(used[v[a[i]][j]])f++;
      }
      if(!f)used[a[i]]=1,sum++;
    }
    r(i,n) swap(a[i],a[xor128()%n]);
    ans=max(ans,sum);
  }
  return ans;
}

int main(){
  cin>>n>>m;
  r(i,m){
    int a,b;
    cin>>a>>b;a--;b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  cout<<max_ind()<<endl;
}

Submission Info

Submission Time
Task G - Mixture Drug
User c7c7
Language C++14 (GCC 5.4.1)
Score 600
Code Size 986 Byte
Status AC
Exec Time 1724 ms
Memory 384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 51
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_4.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 70 ms 256 KB
sample_02.txt AC 17 ms 256 KB
sample_03.txt AC 446 ms 256 KB
subtask_1_1.txt AC 17 ms 256 KB
subtask_1_10.txt AC 759 ms 256 KB
subtask_1_11.txt AC 176 ms 256 KB
subtask_1_12.txt AC 697 ms 256 KB
subtask_1_13.txt AC 544 ms 256 KB
subtask_1_14.txt AC 558 ms 256 KB
subtask_1_15.txt AC 406 ms 256 KB
subtask_1_16.txt AC 883 ms 256 KB
subtask_1_17.txt AC 953 ms 256 KB
subtask_1_18.txt AC 1198 ms 256 KB
subtask_1_19.txt AC 627 ms 256 KB
subtask_1_2.txt AC 494 ms 256 KB
subtask_1_20.txt AC 838 ms 256 KB
subtask_1_21.txt AC 1103 ms 256 KB
subtask_1_22.txt AC 1272 ms 256 KB
subtask_1_23.txt AC 307 ms 384 KB
subtask_1_24.txt AC 620 ms 256 KB
subtask_1_25.txt AC 648 ms 256 KB
subtask_1_26.txt AC 679 ms 256 KB
subtask_1_27.txt AC 656 ms 256 KB
subtask_1_28.txt AC 797 ms 256 KB
subtask_1_29.txt AC 1073 ms 256 KB
subtask_1_3.txt AC 1276 ms 256 KB
subtask_1_30.txt AC 98 ms 256 KB
subtask_1_31.txt AC 508 ms 256 KB
subtask_1_32.txt AC 674 ms 256 KB
subtask_1_33.txt AC 1110 ms 256 KB
subtask_1_34.txt AC 860 ms 256 KB
subtask_1_35.txt AC 964 ms 256 KB
subtask_1_36.txt AC 1227 ms 256 KB
subtask_1_37.txt AC 1724 ms 256 KB
subtask_1_38.txt AC 1593 ms 256 KB
subtask_1_39.txt AC 1631 ms 256 KB
subtask_1_4.txt AC 1588 ms 256 KB
subtask_1_40.txt AC 1630 ms 256 KB
subtask_1_41.txt AC 1570 ms 256 KB
subtask_1_42.txt AC 1280 ms 256 KB
subtask_1_43.txt AC 884 ms 256 KB
subtask_1_44.txt AC 830 ms 256 KB
subtask_1_45.txt AC 768 ms 256 KB
subtask_1_46.txt AC 558 ms 256 KB
subtask_1_47.txt AC 1203 ms 256 KB
subtask_1_48.txt AC 947 ms 256 KB
subtask_1_5.txt AC 618 ms 256 KB
subtask_1_6.txt AC 689 ms 256 KB
subtask_1_7.txt AC 653 ms 256 KB
subtask_1_8.txt AC 705 ms 256 KB
subtask_1_9.txt AC 721 ms 256 KB