Submission #332256

#	Time	Username	Problem	Language	Result	Execution time	Memory
332256		a_player	Colors (RMI18_colors)	C++14	0 / 100	993 ms	3108 KiB

colors

  #include <bits/stdc++.h>

  using namespace std;

  const int nax=1e5+5;
  vector<int> grafo[nax];
  int a[nax],b[nax];
  int ind[nax];
  bool vv[nax];
  bool p[nax];
  bool cmp(int u, int v){
    return b[u]>b[v];
  }
  bool dfs(int n, int in){
    if(a[n]==b[in])return true;
    if(vv[n])return false;
    vv[n]=1;
    for(int x:grafo[n])
      if((a[x]>b[in]&&!p[x])||(a[x]==b[in]))
        if(dfs(x,in)){
          a[x]=b[in];
          return true;
        }


return false;
  }
  void solve(){
  for(int i=0;i<nax;i++){
    p[i]=0;
  grafo[i].clear();
  }
  int n,m;
  cin>>n>>m;
  for(int i=0;i<n;i++)cin>>a[i];
  for(int i=0;i<n;i++)cin>>b[i];
  for(int i=0;i<m;i++){
  int u,v;
  cin>>u>>v;
  u--,v--;
  grafo[u].push_back(v);
  grafo[v].push_back(u);
  }


  iota(ind,ind+n,0);
  sort(ind,ind+n,cmp);
  for(int i=0;i<n;i++){
    for(int i=0;i<n;i++)vv[i]=0;
    int x=ind[i];
    if(!dfs(x,x)){
      cout<<0<<endl;
      return;
    }
    p[x]=1;

  }



  for(int i=0;i<n;i++)if(a[i]!=b[i]){
    cout<<0<<endl;
    return;
  }

  cout<<1<<endl;
  }

  int main(){
  int tt;
  cin>>tt;
  while(tt--)solve();
  }

• Subtask 1: 0 / 15
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 10
• Subtask 8: 0 / 22