oj.uz

답안 #361457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
361457 2021-01-30T09:11:42 Z Thistle Amusement Park (JOI17_amusement_park) C++14
0 / 100
 39 ms 8272 KB 
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define vec vector
#define vi vec<ll>
#define pb emplace_back
#define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),0,(n))
#define siz(a) int((a).size())
#define all(a) (a).begin(), (a).end()


void Joi(int N, int M, int A[], int B[], long long X, int T) {
  int n=N;
  vec<vi>e(n,vi()),f(n,vi()),h(n,vi());
  rep(i,M){
    f[A[i]].pb(B[i]);
    f[B[i]].pb(A[i]);
  }
  vec<bool>used(n,0);
  auto dfs=[&](int x,auto& dfs)->void{
    used[x]=1;
    for(auto g:f[x]){
      if(!used[g]){
        e[x].pb(g);h[x].pb(g);h[g].pb(x);
        dfs(g,dfs);
      }
    }
  };
  dfs(0,dfs);
  queue<int>se;rep(i,60) se.push(i);
  set<int>se2;
  vec<set<int>>po(n,set<int>());
  vi num(n,0),tr(n,-1);
  auto dfs2=[&](int x,auto& dfs2)->void{
    if(!se.empty()) {
      num[x]=se.front();se.pop();
      tr[x]=0;
      se2.insert(x);
    }
    for(auto g:e[x]) dfs2(g,dfs2);
  };
  dfs2(0,dfs2);
  rep(i,n) if(!tr[i]) po[i]=se2;
  auto dfs3=[&](int x,auto& dfs3)->void{
    if(tr[x]<0){
      for(auto g:e[x]) if(~tr[g]){
        int leaf=-1;
        auto dfs4=[&](int x,int p,auto& dfs4)->void{
          int sum=0;
          for(auto r:h[x]) {
            if(r==p||po[g].find(r)==po[g].end()) continue;
            sum++;
            dfs4(r,x,dfs4);
          }
          if(!sum) leaf=x;
        };dfs4(g,-1,dfs4);
        for(auto g:po[g]){
          if(g!=leaf) po[x].insert(g);
          else num[x]=num[g];
        }
        tr[x]=tr[g]+1;
      }
    }
    for(auto g:e[x]) dfs3(g,dfs3);
  };
  rep(i,n) MessageBoard(i,(X>>num[i])&1);
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define vec vector
#define vi vec<ll>
#define pb emplace_back
#define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),0,(n))
#define siz(a) int((a).size())
#define all(a) (a).begin(), (a).end()


long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  int n=N;
  vec<vi>e(n,vi()),f(n,vi()),h(n,vi());
  rep(i,M){
    f[A[i]].pb(B[i]);
    f[B[i]].pb(A[i]);
  }
  vec<bool>used(n,0);
  auto dfs=[&](int x,auto& dfs)->void{
    used[x]=1;
    for(auto g:f[x]){
      if(!used[g]){
        e[x].pb(g);h[x].pb(g);h[g].pb(x);
        dfs(g,dfs);
      }
    }
  };
  dfs(0,dfs);
  queue<int>se;rep(i,60) se.push(i);
  set<int>se2;
  vec<set<int>>po(n,set<int>());
  vi num(n,0),tr(n,-1);
  auto dfs2=[&](int x,auto& dfs2)->void{
    if(!se.empty()) {
      num[x]=se.front();se.pop();
      tr[x]=0;
      se2.insert(x);
    }
    for(auto g:e[x]) dfs2(g,dfs2);
  };
  dfs2(0,dfs2);
  rep(i,n) if(!tr[i]) po[i]=se2;
  auto dfs3=[&](int x,auto& dfs3)->void{
    if(tr[x]<0){
      for(auto g:e[x]) if(~tr[g]){
        int leaf=-1;
        auto dfs4=[&](int x,int p,auto& dfs4)->void{
          int sum=0;
          for(auto r:h[x]) {
            if(r==p||po[g].find(r)==po[g].end()) continue;
            sum++;
            dfs4(r,x,dfs4);
          }
          if(!sum) leaf=x;
        };dfs4(g,-1,dfs4);
        for(auto g:po[g]){
          if(g!=leaf) po[x].insert(g);
          else num[x]=num[g];
        }
        tr[x]=tr[g]+1;
      }
    }
    for(auto g:e[x]) dfs3(g,dfs3);
  };

  ll ans=ll(V)<<num[P];
  auto dfs5=[&](int x,int p,auto& dfs5)->void{
    for(auto g:h[x]){
      if(g==p||po[P].find(x)==po[P].end())continue;
      ll t=Move(g);
      ans|=(t<<num[g]);
      dfs5(g,x,dfs5);
      
    }
    if(~p) Move(p);
  };dfs5(P,-1,dfs5);
  return ans;
}

Compilation message

Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
      |                           ^
Joi.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
Joi.cpp:17:3: note: in expansion of macro 'rep'
   17 |   rep(i,M){
      |   ^~~
Joi.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
      |                           ^
Joi.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
Joi.cpp:32:16: note: in expansion of macro 'rep'
   32 |   queue<int>se;rep(i,60) se.push(i);
      |                ^~~
Joi.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
      |                           ^
Joi.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
Joi.cpp:45:3: note: in expansion of macro 'rep'
   45 |   rep(i,n) if(!tr[i]) po[i]=se2;
      |   ^~~
Joi.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
      |                           ^
Joi.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
Joi.cpp:68:3: note: in expansion of macro 'rep'
   68 |   rep(i,n) MessageBoard(i,(X>>num[i])&1);
      |   ^~~
Joi.cpp:46:8: warning: variable 'dfs3' set but not used [-Wunused-but-set-variable]
   46 |   auto dfs3=[&](int x,auto& dfs3)->void{
      |        ^~~~

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
      |                           ^
Ioi.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
Ioi.cpp:17:3: note: in expansion of macro 'rep'
   17 |   rep(i,M){
      |   ^~~
Ioi.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
      |                           ^
Ioi.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
Ioi.cpp:32:16: note: in expansion of macro 'rep'
   32 |   queue<int>se;rep(i,60) se.push(i);
      |                ^~~
Ioi.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
      |                           ^
Ioi.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
Ioi.cpp:45:3: note: in expansion of macro 'rep'
   45 |   rep(i,n) if(!tr[i]) po[i]=se2;
      |   ^~~
Ioi.cpp:46:8: warning: variable 'dfs3' set but not used [-Wunused-but-set-variable]
   46 |   auto dfs3=[&](int x,auto& dfs3)->void{
      |        ^~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1172 KB Output is correct
2 Incorrect 2 ms 1128 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1124 KB Output is correct
2 Correct 2 ms 1128 KB Output is correct
3 Incorrect 2 ms 1152 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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