Submission #295921

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
295921	2020-09-10T06:14:53 Z	Hemimor	Regions (IOI09_regions)	C++14	30 / 100	5140 ms	131076 KB

regions

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Segment_Tree{
	private:
	int n;
	vi date;
	public:
	Segment_Tree(int n_){
		n=1;
		while(n<n_) n*=2;
		date=vi(2*n-1);
	}
	void Update(int k,int x){
		k+=n-1;
		date[k]+=x;
		while(k>0){
			k=(k-1)/2;
			date[k]=date[k*2+1]+date[k*2+2];
		}
	}
	int Query(int a,int b){
		a+=n-1;b+=n-1;
		int m=0;
		while(a<b){
			if(a%2==0) m+=date[a++];
			if(b%2==0) m+=date[--b];
			a/=2;b/=2;
		}
		return m;
	}
	int Open(int k){return date[k+n-1];}
};

const int M=200;
int n,m,q,id=0;
vvi g,b;
vi a,par,num,lt,rt,c,d;
map<P,int> mp;

void dfs(int v){
	lt[v]=id++;
	for(auto u:g[v]) dfs(u);
	rt[v]=id;
}

void DFS(int v,int t){
	if(a[v]==t){
		c[v]++;
		d[v]++;
	}
	for(auto u:g[v]){
		d[u]=d[v];
		DFS(u,t);
		c[v]+=c[u];
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&q);
	Segment_Tree st(n);
	g=vvi(n);
	b=vvi(m);
	a=lt=rt=vi(n);
	par=vi(n,-1);
	num=vi(m);
	for(int i=0;i<n;i++){
		if(i){
			scanf("%d",&par[i]);
			par[i]--;
			g[par[i]].push_back(i);
		}
		scanf("%d",&a[i]);
		a[i]--;
		num[a[i]]++;
		b[a[i]].push_back(i);
	}
	dfs(0);
	for(int i=0;i<m;i++) if(a[i]>M){
		c=d=vi(n);
		DFS(0,i);
		vi tc(m),td(m);
		for(int j=0;j<n;j++) if(a[j]!=i){
			tc[a[j]]+=c[j];
			td[a[j]]+=d[j];
		}
		for(int j=0;j<m;j++) if(j!=i){
			mp[{j,i}]=tc[j];
			mp[{i,j}]=td[j];
		}
	}
	for(int i=0;i<q;i++){
		int x,y,res=0;
		scanf("%d%d",&x,&y);
		x--,y--;
		if(mp.find({x,y})!=mp.end()) res=mp[{x,y}];
		else{
			for(auto j:b[y]) st.Update(lt[j],1);
			for(auto j:b[x]) res+=st.Query(lt[j],rt[j]);
			for(auto j:b[y]) st.Update(lt[j],-1);
		}
		mp[{x,y}]=res;
		printf("%d\n",res);
		fflush(stdout);
	}
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |  scanf("%d%d%d",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:103:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |    scanf("%d",&par[i]);
      |    ~~~~~^~~~~~~~~~~~~~
regions.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
regions.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	9 ms	384 KB	Output is correct
6	Correct	28 ms	1792 KB	Output is correct
7	Correct	32 ms	632 KB	Output is correct
8	Correct	36 ms	632 KB	Output is correct
9	Correct	78 ms	4636 KB	Output is correct
10	Correct	235 ms	9748 KB	Output is correct
11	Correct	202 ms	3960 KB	Output is correct
12	Correct	410 ms	12280 KB	Output is correct
13	Correct	360 ms	7304 KB	Output is correct
14	Correct	434 ms	3600 KB	Output is correct
15	Correct	668 ms	7964 KB	Output is correct

Subtask #2

15.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3260 ms	9304 KB	Output is correct
2	Correct	2730 ms	9448 KB	Output is correct
3	Correct	5140 ms	15032 KB	Output is correct
4	Runtime error	1773 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
5	Runtime error	1188 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
6	Runtime error	1905 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
7	Runtime error	1501 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Runtime error	1112 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Runtime error	1716 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Runtime error	953 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
11	Runtime error	1456 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
12	Runtime error	2405 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Runtime error	1704 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	1909 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Runtime error	1132 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Runtime error	1093 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	1034 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)