oj.uz

Submission #830142

# Submission time Handle Problem Language Result Execution time Memory
830142 2023-08-18T19:59:41 Z FEDIKUS Amusement Park (JOI17_amusement_park) C++17
0 / 100
 20 ms 5200 KB 
#include "Joi.h"
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

namespace{
  const int maxn=10010;
  const int logg=60;

  int boja[maxn];
  int bio[maxn];
  int p[maxn];
  vector<int> g[maxn];
  vector<int> stablo[maxn];
  int deg[maxn];
  set<int> lisce;
  int klk=0;

  bool dfs(int node){
    bio[node]=1;
    klk++;
    boja[node]=klk-1;

    if(klk==60) return true;
    for(int i:g[node]){
      if(bio[i]) continue;
      stablo[node].push_back(i);
      p[i]=node;
      if(dfs(i)) return true;
    }
    return false;
  }

  void dfs2(int node){
    bio[node]=2;
    for(int i:g[node]){
      if(bio[i]==1){
        p[node]=i;
        p[i]=-1;

        dfs2(i);

        p[node]=-1;
        p[i]=node;
      }else if(bio[i]==0){
        int uzimam=-1;
        if(*lisce.begin()==node){
          uzimam=*(++lisce.begin());
        }else uzimam=*lisce.begin();

        boja[i]=boja[uzimam];

        p[node]=i;
        p[i]=-1;

        deg[p[uzimam]]--;
        deg[uzimam]--;
        lisce.erase(uzimam);
        if(deg[p[uzimam]]==1) lisce.emplace(p[uzimam]);
        lisce.emplace(i);
        if(deg[node]==1) lisce.erase(node);
        deg[node]++;
        deg[i]++;
        if(deg[i]==1) lisce.emplace(i);

        dfs2(i);

        if(deg[i]==1) lisce.erase(i);
        deg[node]--;
        deg[i]--;
        if(deg[node]==1) lisce.emplace(node);
        lisce.erase(i);
        if(deg[p[uzimam]]==1) lisce.erase(p[uzimam]);
        lisce.emplace(uzimam);
        deg[uzimam]++;
        deg[p[uzimam]]++;


        p[node]=-1;
        p[i]=node;
      }
    }
  }

}

void Joi(int n, int m, int a[], int b[], ll x, int t) {
  for(int i=0;i<m;i++){
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
  }
  p[0]=-1;
  dfs(0);
  for(int i=0;i<n;i++) if(bio[i]==1) for(int j:stablo[i]) deg[i]++,deg[j]++;
  for(int i=0;i<n;i++) if(bio[i]==1 && deg[i]==1) lisce.emplace(i);
  dfs2(0);

  for(int i=0;i<n;i++) MessageBoard(i,((1LL<<boja[i])&x)!=0);
}

#include "Ioi.h"
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

namespace{
  const int maxn=10010;
  const int logg=60;

  int boja[maxn];
  int bio[maxn];
  int p[maxn];
  vector<int> g[maxn];
  vector<int> stablo[maxn];
  int deg[maxn];
  set<int> lisce;
  int klk=0;
  set<int> imam;
  int poc;
  ll res=0;
  set<int> koristio;

  bool dfs(int node){
    bio[node]=1;
    imam.emplace(node);
    klk++;
    boja[node]=klk-1;

    if(klk==60) return true;
    for(int i:g[node]){
      if(bio[i]) continue;
      stablo[node].push_back(i);
      p[i]=node;
      if(dfs(i)) return true;
    }
    return false;
  }

  bool dfs2(int node){

    if(node==poc){
      return true;
    }

    bio[node]=2;
    for(int i:g[node]){
      if(bio[i]==1){
        p[node]=i;
        p[i]=-1;

        if(dfs2(i)) return true;

        p[node]=-1;
        p[i]=node;
      }else if(bio[i]==0){
        cout<<node<<" "<<i<<"\n";
        int uzimam=-1;
        if(*lisce.begin()==node){
          uzimam=*(++lisce.begin());
        }else uzimam=*lisce.begin();

        assert(lisce.size()>=2);
        
        assert(uzimam!=node);
        assert(p[uzimam]!=uzimam);
        assert(i!=uzimam);

        boja[i]=boja[uzimam];

        p[node]=i;
        p[i]=-1;

        assert(deg[uzimam]==1);
        assert(imam.find(uzimam)!=imam.end());
        imam.erase(uzimam);
        assert(imam.find(i)==imam.end());
        assert(p[uzimam]!=i);
        imam.emplace(i);
        deg[p[uzimam]]--;
        deg[uzimam]--;
        lisce.erase(uzimam);
        if(deg[p[uzimam]]<=0){
          cout<<uzimam<<" "<<i<<"\n";
          cout<<p[uzimam]<<deg[p[uzimam]]<<"\n";
        }
        assert(deg[p[uzimam]]>0);
        if(deg[p[uzimam]]==1) lisce.emplace(p[uzimam]);
        if(deg[node]==1) lisce.erase(node);
        deg[node]++;
        deg[i]++;
        if(deg[i]==1) lisce.emplace(i);

        if(dfs2(i)) return true;

        if(deg[i]==1) lisce.erase(i);
        deg[i]--;
        deg[node]--;
        if(deg[node]==1) lisce.emplace(node);
        if(deg[p[uzimam]]==1) lisce.erase(p[uzimam]);
        lisce.emplace(uzimam);
        deg[uzimam]++;
        deg[p[uzimam]]++;
        imam.erase(i);
        imam.emplace(uzimam);


        p[node]=-1;
        p[i]=node;
      }
    }
    return false;
  }

  int v;
  int klk2=0;

  void uradi(int node){
    klk2++;
    //assert(koristio.find(boja[node])==koristio.end());
    koristio.emplace(boja[node]);
    res+=(1ll<<boja[node])*v;
    bio[node]=3;
    for(int i:g[node]){
      if(bio[i]==3) continue;
      if(imam.find(i)==imam.end()) continue;

      v=Move(i);
      uradi(i);
      v=Move(node);
    }
  }

}

ll Ioi(int n, int m, int a[], int b[], int _poc, int _v, int t){
  poc=_poc;
  v=_v;
  for(int i=0;i<m;i++){
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
  }
  p[0]=-1;
  dfs(0);
  assert(imam.size()==60);
  if(imam.find(poc)==imam.end()){
    for(int i=0;i<n;i++) if(bio[i]==1) for(int j:stablo[i]) deg[i]++,deg[j]++;
    for(int i=0;i<n;i++) if(bio[i]==1 && deg[i]==1) lisce.emplace(i);
    for(int i:lisce) cout<<i<<" "; cout<<"\n";
    dfs2(0);
  }
  assert(imam.size()==60);
  uradi(poc);
  assert(koristio.size()==60);
  cout<<res<<"\n";
  return res;
}

Compilation message

Ioi.cpp: In function 'll Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:149:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  149 |     for(int i:lisce) cout<<i<<" "; cout<<"\n";
      |     ^~~
Ioi.cpp:149:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  149 |     for(int i:lisce) cout<<i<<" "; cout<<"\n";
      |                                    ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1544 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4896 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1536 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 5200 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4940 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -