답안 #893521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
893521	2023-12-27T06:14:34 Z	Faisal_Saqib	Split the Attractions (IOI19_split)	C++17	컴파일 오류	0 ms	0 KB

split

//IOI 2019
//Split - Version 1.1 - First Solution
//Current Version: 9 May 2019
//Older version: 31 March 2019
//Mahdi Safarnejad Boroujeni

#define forn(i, n) for (int i = 0; i < int(n); i++)

#include "split.h"

#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 1000000+110;
typedef pair<int,int> intpair;

int n;
vector<int> a[maxn];
vector<int> result(maxn);
intpair b[3];

bool finishedPhase1 = false;

int mark[maxn], size[maxn];
int counter=1, startingtime[maxn], mintime[maxn];

int dfs2(int v, int goal, int comp, bool ignore_st=false) {
	int sum=1;
	mark[v]=2;
	result[v]=comp;
	goal -= 1;
	forn(i, a[v].size())
    if (goal > 0 && mark[a[v][i]] < 2 && (ignore_st || (startingtime[a[v][i]] > startingtime[v]))) {
        int thisSize = dfs2(a[v][i], goal, comp, ignore_st);
        sum += thisSize;
        goal -= thisSize;
    }
    return sum;
}

void dfs(int v, int par) {
    mark[v]=1;
    size[v]=1;
    startingtime[v] = counter++;
    mintime[v] = startingtime[v];
    int removablesSum=0;
    forn(i, a[v].size())
        if (!mark[a[v][i]]) {
            dfs(a[v][i], v);
            if (finishedPhase1)
            	return;
            size[v]+=size[a[v][i]];
            mintime[v] = min(mintime[v], mintime[a[v][i]]);
            if (mintime[a[v][i]] < startingtime[v])
                removablesSum += size[a[v][i]];
        } else if (a[v][i]!=par) {
            mintime[v] = min(mintime[v], mintime[a[v][i]]);
        }
    if (size[v] >= b[0].first) {
    	finishedPhase1 = true;
    	if (n - size[v] + removablesSum < b[0].first)
    		return; //No Solution
    	int element = 0;
    	if (n - size[v] + removablesSum < b[1].first)
    		element = 1;
    	result[v] = b[element].second;
        mark[v] = 2;
    	int goal = b[element].first - 1;
    	forn(i, a[v].size()) {
    		if (mark[a[v][i]] < 2 && goal > 0 && mintime[a[v][i]] >= startingtime[v] && startingtime[a[v][i]] > startingtime[v])
    			goal -= dfs2(a[v][i], goal, b[element].second);
    	}
    	forn(i, a[v].size()) {
    		if (mark[a[v][i]] < 2 && goal > 0 && mintime[a[v][i]] < startingtime[v] && startingtime[a[v][i]] > startingtime[v])
    			goal -= dfs2(a[v][i], goal, b[element].second);
    	}
    	dfs2(0, b[1-element].first, b[1-element].second, true);
    	forn(i, n)
    		if (result[i]==0)
    			result[i]=b[2].second;
    }
}

vector <int> find_split(int n_, int a_, int b_, int c_, vector <int> p, vector <int> q) {
	n = n_;
    b[0]=intpair(a_, 1); b[1]=intpair(b_, 2); b[2]=intpair(c_, 3);
	sort(b, b+3);
	forn(i, p.size()) {
		a[p[i]].push_back(q[i]);
		a[q[i]].push_back(p[i]);
	}
    dfs(0, -1);
		result.resize(n);
    return result;
}

Compilation message

split.cpp: In function 'void dfs(int, int)':
split.cpp:44:5: error: reference to 'size' is ambiguous
   44 |     size[v]=1;
      |     ^~~~
In file included from /usr/include/c++/10/vector:69,
                 from split.h:5,
                 from split.cpp:9:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
split.cpp:25:17: note:                 'int size [1000110]'
   25 | int mark[maxn], size[maxn];
      |                 ^~~~
split.cpp:53:13: error: reference to 'size' is ambiguous
   53 |             size[v]+=size[a[v][i]];
      |             ^~~~
In file included from /usr/include/c++/10/vector:69,
                 from split.h:5,
                 from split.cpp:9:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
split.cpp:25:17: note:                 'int size [1000110]'
   25 | int mark[maxn], size[maxn];
      |                 ^~~~
split.cpp:53:22: error: reference to 'size' is ambiguous
   53 |             size[v]+=size[a[v][i]];
      |                      ^~~~
In file included from /usr/include/c++/10/vector:69,
                 from split.h:5,
                 from split.cpp:9:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
split.cpp:25:17: note:                 'int size [1000110]'
   25 | int mark[maxn], size[maxn];
      |                 ^~~~
split.cpp:56:34: error: reference to 'size' is ambiguous
   56 |                 removablesSum += size[a[v][i]];
      |                                  ^~~~
In file included from /usr/include/c++/10/vector:69,
                 from split.h:5,
                 from split.cpp:9:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
split.cpp:25:17: note:                 'int size [1000110]'
   25 | int mark[maxn], size[maxn];
      |                 ^~~~
split.cpp:60:9: error: reference to 'size' is ambiguous
   60 |     if (size[v] >= b[0].first) {
      |         ^~~~
In file included from /usr/include/c++/10/vector:69,
                 from split.h:5,
                 from split.cpp:9:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
split.cpp:25:17: note:                 'int size [1000110]'
   25 | int mark[maxn], size[maxn];
      |                 ^~~~
split.cpp:62:14: error: reference to 'size' is ambiguous
   62 |      if (n - size[v] + removablesSum < b[0].first)
      |              ^~~~
In file included from /usr/include/c++/10/vector:69,
                 from split.h:5,
                 from split.cpp:9:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
split.cpp:25:17: note:                 'int size [1000110]'
   25 | int mark[maxn], size[maxn];
      |                 ^~~~
split.cpp:65:14: error: reference to 'size' is ambiguous
   65 |      if (n - size[v] + removablesSum < b[1].first)
      |              ^~~~
In file included from /usr/include/c++/10/vector:69,
                 from split.h:5,
                 from split.cpp:9:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
split.cpp:25:17: note:                 'int size [1000110]'
   25 | int mark[maxn], size[maxn];
      |                 ^~~~