oj.uz

답안 #829912

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
829912 2023-08-18T15:50:16 Z FEDIKUS Amusement Park (JOI17_amusement_park) C++17
10 / 100
 28 ms 5644 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;

  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;

        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;
        imam.erase(uzimam);
        imam.emplace(i);
        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);

        if(dfs2(i)) return true;

        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]]++;
        imam.erase(i);
        imam.emplace(uzimam);


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

  int v;

  void uradi(int 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);
  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);
    dfs2(0);
  }
  uradi(poc);
  return res;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1544 KB Output is correct
2 Correct 2 ms 1544 KB Output is correct
3 Correct 2 ms 1552 KB Output is correct
4 Correct 1 ms 1604 KB Output is correct
5 Correct 1 ms 1548 KB Output is correct
6 Correct 2 ms 1604 KB Output is correct
7 Correct 2 ms 1544 KB Output is correct
8 Correct 2 ms 1544 KB Output is correct
9 Correct 2 ms 1672 KB Output is correct
10 Correct 2 ms 1484 KB Output is correct
11 Incorrect 3 ms 1996 KB Wrong Answer [7]
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 5168 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 1 ms 1532 KB Output is correct
4 Correct 3 ms 2068 KB Output is correct
5 Correct 2 ms 2092 KB Output is correct
6 Correct 3 ms 2088 KB Output is correct
7 Correct 3 ms 2092 KB Output is correct
8 Correct 3 ms 2236 KB Output is correct
9 Correct 11 ms 5040 KB Output is correct
10 Correct 10 ms 4324 KB Output is correct
11 Correct 12 ms 5644 KB Output is correct
12 Correct 1 ms 1604 KB Output is correct
13 Correct 1 ms 1548 KB Output is correct
14 Correct 2 ms 1548 KB Output is correct
15 Correct 1 ms 1540 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 5160 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 5068 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -