제출 #1305495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305495		coolboy19521	Stranded Far From Home (BOI22_island)	C++20	0 / 100	90 ms	14680 KiB

island

#include "bits/stdc++.h"

#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;i>=(a);i--)
#define R0F(i,a)ROF(i,0,a)
#define REP(a)F0R(_,a)

using namespace std;

const int mxn=2e5+20;

vector<int> aj[mxn];
bool mark[mxn];
int s[mxn];

struct{
	long long val[mxn];
	int ar[mxn];
	void init(int n){
		fill_n(ar,n,-1);
		memcpy(val,s,sizeof(val));
	}
	int find(int u){
		if(ar[u]<0)return u;
		else return ar[u]=find(ar[u]);
	}
	void unite(int u,int v){
		v=find(v);
		if(s[u]>val[v]){
			mark[v]=true;
			return;
		}
		u=find(u);
		if(u==v)return;
		if(ar[u]>ar[v])swap(u,v);
		val[u]+=val[v],ar[u]+=ar[v],ar[v]=u;
	}
}DSU;

int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n,m;cin>>n>>m;
	F0R(i,n)cin>>s[i];
	DSU.init(n);
	REP(m){
		int a,b;cin>>a>>b;
		a--,b--;
		if(s[a]<s[b])swap(a,b);
		aj[a].push_back(b);
	}
	vector<pair<int,int>>vp;
	F0R(i,n)vp.emplace_back(s[i],i);
	sort(begin(vp),end(vp));
	for(auto&pr:vp){
		int w=pr.first,u=pr.second;
		for(int v:aj[u])DSU.unite(u,v);
	}
	F0R(i,n)cout<<(mark[DSU.find(i)]?0:1);cout<<'\n';
}

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

In file included from /usr/include/string.h:548,
                 from /usr/include/c++/13/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:121,
                 from island.cpp:1:
In function 'void* memcpy(void*, const void*, size_t)',
    inlined from 'void<unnamed struct>::init(int)' at island.cpp:22:9,
    inlined from 'int main()' at island.cpp:45:10:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:29:33: warning: 'void* __builtin_memcpy(void*, const void*, long unsigned int)' reading 1600160 bytes from a region of size 800080 [-Wstringop-overread]
   29 |   return __builtin___memcpy_chk (__dest, __src, __len,
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
   30 |                                  __glibc_objsize0 (__dest));
      |                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~
island.cpp: In function 'int main()':
island.cpp:15:5: note: source object 's' of size 800080
   15 | int s[mxn];
      |     ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35