Submission #294538

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
294538	2020-09-09T04:12:22 Z	nandonathaniel	The Potion of Great Power (CEOI20_potion)	C++14	Compilation error	0 ms	0 KB

potion

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

bitset<100005> stat;
 
int main(){
	int n,D,u,q,d,a,b,r,s;
	scanf("%d%d%d%d",&n,&D,&u,&q);
	int h[n],C[n];
	vector<pii> adj[n];
	vector<vector<int> > preCompute[n];
	for(int i=0;i<n;i++)scanf("%d",&h[i]);
	for(int i=1;i<=u;i++){
		scanf("%d%d",&r,&s);
		adj[r].push_back({s,i});
		adj[s].push_back({r,i});
	}
	for(int i=0;i<n;i++){
		C[i]=(int)sqrt((int)adj[i].size());
		if(C[i]==0)C[i]=1;
		set<int> S;
		preCompute[i].push_back(vector<int>());
		for(int j=0;j<adj[i].size();j++){
			if(S.count(adj[i][j].first)){
				S.erase(adj[i][j].first);
			}
			else S.insert(adj[i][j].first);
			if((j+1)%C[i]==0){
				preCompute[i].push_back(vector<int>());
				for(int isi : S)preCompute[i].back().push_back(isi);
			}
		}
	}
	while(q--){
		scanf("%d%d%d",&a,&b,&d);
		int ans=1e9;
		if(d==0){
			printf("%d\n",ans);
			fflush(stdout);
			continue;
		}
		int ki=0,ka=adj[a].size()-1,res=-1;
		while(ki<=ka){
			int mid=(ki+ka)/2;
			if(adj[a][mid].second<=d){
				res=mid;
				ki=mid+1;
			}
			else ka=mid-1;
		}
		stat.reset();
		vector<int> A;
		if(res!=-1){
			for(auto isi : preCompute[a][res/C[a]])stat[isi]=true;
			for(int i=(res/C[a])*C[a];i<=res;i++){
				stat[adj[a][i].first]=stat[adj[a][i].first]^1;
			}
			for(auto isi : preCompute[a][res/C[a]]){
				if(stat[isi])A.push_back(h[isi]);
			}
			for(int i=(res/C[a])*C[a];i<=res;i++){
				if(stat[adj[a][i].first])A.push_back(h[adj[a][i].first]);
			}
		}
		ki=0;ka=adj[b].size()-1;res=-1;
		while(ki<=ka){
			int mid=(ki+ka)/2;
			if(adj[b][mid].second<=d){
				res=mid;
				ki=mid+1;
			}
			else ka=mid-1;
		}
		stat.reset();
		vector<int> B;
		if(res!=-1){
			for(auto isi : preCompute[b][res/C[b]])stat[isi]=true;
			for(int i=(res/C[b])*C[b];i<=res;i++){
				stat[adj[b][i].first]=stat[adj[b][i].first]^1;
			}
			for(auto isi : preCompute[b][res/C[b]]){
				if(stat[isi])B.push_back(h[isi]);
			}
			for(int i=(res/C[b])*C[b];i<=res;i++){
				if(stat[adj[b][i].first])B.push_back(h[adj[b][i].first]);
			}
		}
		sort(A.begin(),A.end());
		sort(B.begin(),B.end());
		int x=0,y=0;
		while(x<(int)A.size() && y<(int)B.size()){
			ans=min(ans,abs(A[x]-B[y]));
			if(A[x]<B[y])x++;
			else y++;
		}
		printf("%d\n",ans);
		fflush(stdout);
	}
	return 0;
}
 

Compilation message

potion.cpp: In function 'int main()':
potion.cpp:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int j=0;j<adj[i].size();j++){
      |               ~^~~~~~~~~~~~~~
potion.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 |  scanf("%d%d%d%d",&n,&D,&u,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |  for(int i=0;i<n;i++)scanf("%d",&h[i]);
      |                      ~~~~~^~~~~~~~~~~~
potion.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |   scanf("%d%d",&r,&s);
      |   ~~~~~^~~~~~~~~~~~~~
potion.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |   scanf("%d%d%d",&a,&b,&d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
/tmp/ccQErYVK.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc4EhL3r.o:potion.cpp:(.text.startup+0x0): first defined here
/tmp/ccQErYVK.o: In function `main':
grader.cpp:(.text.startup+0xde): undefined reference to `init(int, int, int*)'
grader.cpp:(.text.startup+0x167): undefined reference to `curseChanges(int, int*, int*)'
grader.cpp:(.text.startup+0x1c1): undefined reference to `question(int, int, int)'
collect2: error: ld returned 1 exit status