제출 #978786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978786		AdamGS	Split the Attractions (IOI19_split)	C++17	40 / 100	85 ms	29640 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
vector<int>V[LIM], P[LIM], G[LIM], ans;
vector<pair<int,int>>S;
int pre[LIM], odl[LIM], ile[LIM], lpre, X;
void DFS(int x) {
  pre[x]=++lpre;
  for(auto i : V[x]) {
    if(!pre[i]) {
      P[x].pb(i);
      DFS(i);
    } else if(pre[i]<pre[x]) G[x].pb(i);
  }
}
void DFS2(int x) {
  ile[x]=1;
  for(auto i : P[x]) {
    odl[i]=odl[x]+1;
    DFS2(i);
    ile[x]+=ile[i];
  }
}
void DFS3(int x, int k) {
  if(!X || ans[x]) return;
  ans[x]=k;
  --X;
  for(auto i : P[x]) DFS3(i, k);
}
void DFS4(int x, int k) {
  if(ans[x]) return;
  ans[x]=k;
  for(auto i : P[x]) DFS4(i, k);
}
void DFS7(int x, int k) {
  if(X) ans[x]=k; else ans[x]=S[2].nd;
  for(auto i : P[x]) DFS7(i, k);
}
void DFS5(int x, bool c, int k, int p) {
  for(auto i : G[x]) if(odl[i]<k) c=true;
  if(c) {
    if(X) DFS7(x, p);
    return;
  }
  for(auto i : P[x]) DFS5(i, c, k, p);
}
bool DFS6(int x, int k) {
  bool c=true;
  if(S[2].st==0) c=false;
  if(ans[x]==k) c=false;
  for(auto i : P[x]) c&=DFS6(i, k);
  if(c) {
    --S[2].st;
    ans[x]=S[2].nd;
  }
  return c;
}
vector<int>find_split(int n, int a, int b, int c, vector<int>p, vector<int>q) {
  mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
  rep(xd, 20) {
    int root=rng()%n;
    lpre=X=0;
    ans.clear();
    S.clear();
    rep(i, n) {
      V[i].clear();
      G[i].clear();
      P[i].clear();
      pre[i]=odl[i]=ile[i]=0;
    }
    rep(i, n) ans.pb(0);
    S.pb({a, 1});
    S.pb({b, 2});
    S.pb({c, 3});
    sort(all(S));
    rep(i, p.size()) {
      V[p[i]].pb(q[i]);
      V[q[i]].pb(p[i]);
    }
    DFS(root);
    DFS2(root);
    rep(i, n) if(ile[i]>=S[0].st && n-ile[i]>=S[1].st) {
      X=S[0].st;
      DFS3(i, S[0].nd);
      X=S[1].st;
      DFS3(root, S[1].nd);
      rep(j, n) if(!ans[j]) ans[j]=S[2].nd;
      return ans;
    }
    rep(i, n) if(ile[i]>=S[1].st && n-ile[i]>=S[0].st) {
      X=S[1].st;
      DFS3(i, S[1].nd);
      X=S[0].st;
      DFS3(root, S[0].nd);
      rep(j, n) if(!ans[j]) ans[j]=S[2].nd;
      return ans;
    }
    pair<int,int>mi={n, n};
    rep(i, n) if(ile[i]>=S[0].st) mi=min(mi, {ile[i], i});
    if(mi.nd==root) continue;
    X=S[1].st-(n-mi.st);
    DFS4(mi.nd, S[0].nd);
    DFS4(root, S[1].nd);
    for(auto i : P[mi.nd]) DFS5(i, false, odl[mi.nd], S[1].nd);
    if(!X) {
      DFS6(root, S[1].nd);
      return ans;
    }
    rep(i, n) ans[i]=0;
    mi={n, n};
    rep(i, n) if(ile[i]>=S[1].st) mi=min(mi, {ile[i], i});
    if(mi.nd==root) continue;
    X=S[0].st-(n-mi.st);
    DFS4(mi.nd, S[1].nd);
    DFS4(root, S[0].nd);
    for(auto i : P[mi.nd]) DFS5(i, false, odl[mi.nd], S[0].nd);
    if(X) rep(i, n) ans[i]=0;
    else DFS6(root, S[0].nd);
    return ans;
  }
  rep(i, n) ans[i]=0;
  return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
split.cpp:83:5: note: in expansion of macro 'rep'
   83 |     rep(i, p.size()) {
      |     ^~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36