답안 #601675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601675	2022-07-22T09:06:26 Z	CSQ31	Stranded Far From Home (BOI22_island)	C++17	컴파일 오류	0 ms	0 KB

island

//consider scc graph
//u -> v
//if u bad then v must be bad
//so every ingoing edge into v must be good and sum of sub(tree?graph?) must be >= minimal parent
//i dont even need scc,only scc is if all values are equal okay yes
#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define pb push_back
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
const int MAXN = 2e5+5;
int s[MAXN];
vector<int>adj[MAXN],group[MAXN],any[MAXN];
vector<int>gr[MAXN],g[MAXN],ord;
int vis[MAXN],par[MAXN],good[MAXN];

int find(int x){
	if(x==par[x])return x;
	return par[x] = find(par[x]);
}
void unite(int a,int b){
	a = find(a);
	b = find(b);
	if(a==b)return;
	par[a] = b;
}
void dfs(int v){
	vis[v] = 1;
	for(int x:g[v]){
		if(!vis[x])dfs(x);
	}
	ord.pb(v);
	
}
ll dp[MAXN];
int main()
{
	owo
	int n,m,mx = 0;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>s[i];
		par[i] = i;
		mx = max(mx,s[i]);
	}
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		if(s[a] > s[b])adj[a].pb(b);
		if(s[b] > s[a])adj[b].pb(a);
		if(s[a]==s[b])unite(a,b);
		any[a].pb(b);
		any[b].pb(a);
	}
	for(int i=0;i<n;i++){
		ll cur = s[i];
		set<array<ll,2>>S;
		S.insert({s[i],i});
		for(int j=0;j<n;j++)vis[j] = 0;
		while(!S.empty()){
			auto v = *S.begin();
			S.erase(v);
			vis[v[1]] = 1;
			if(v[1] != i){
				if(cur >= v[0])cur+=v[0];
				else break;
			}
			for(int x:any[v[1]])if(!vis[x])S.insert({s[x],x});
		}
		if(cur>=mx)good[i] = 1;
		
	}
	for(int i=0;i<n;i++)cout<<good[i];
	
	
	
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:56:3: error: reference to 'any' is ambiguous
   56 |   any[a].pb(b);
      |   ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:126,
                 from island.cpp:6:
/usr/include/c++/10/any:77:9: note: candidates are: 'class std::any'
   77 |   class any
      |         ^~~
island.cpp:15:34: note:                 'std::vector<int> any [200005]'
   15 | vector<int>adj[MAXN],group[MAXN],any[MAXN];
      |                                  ^~~
island.cpp:57:3: error: reference to 'any' is ambiguous
   57 |   any[b].pb(a);
      |   ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:126,
                 from island.cpp:6:
/usr/include/c++/10/any:77:9: note: candidates are: 'class std::any'
   77 |   class any
      |         ^~~
island.cpp:15:34: note:                 'std::vector<int> any [200005]'
   15 | vector<int>adj[MAXN],group[MAXN],any[MAXN];
      |                                  ^~~
island.cpp:72:14: error: reference to 'any' is ambiguous
   72 |    for(int x:any[v[1]])if(!vis[x])S.insert({s[x],x});
      |              ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:126,
                 from island.cpp:6:
/usr/include/c++/10/any:77:9: note: candidates are: 'class std::any'
   77 |   class any
      |         ^~~
island.cpp:15:34: note:                 'std::vector<int> any [200005]'
   15 | vector<int>adj[MAXN],group[MAXN],any[MAXN];
      |                                  ^~~