Submission #295924

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
295924	2020-09-10T06:17:06 Z	Hemimor	Regions (IOI09_regions)	C++14	30 / 100	6050 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=400;
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	1 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	11 ms	384 KB	Output is correct
6	Correct	22 ms	512 KB	Output is correct
7	Correct	40 ms	632 KB	Output is correct
8	Correct	39 ms	632 KB	Output is correct
9	Correct	69 ms	1272 KB	Output is correct
10	Correct	121 ms	2296 KB	Output is correct
11	Correct	197 ms	2168 KB	Output is correct
12	Correct	267 ms	5112 KB	Output is correct
13	Correct	287 ms	2952 KB	Output is correct
14	Correct	485 ms	3576 KB	Output is correct
15	Correct	869 ms	6328 KB	Output is correct

Subtask #2

15.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3345 ms	9248 KB	Output is correct
2	Correct	3150 ms	8436 KB	Output is correct
3	Correct	6050 ms	13608 KB	Output is correct
4	Runtime error	1793 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
5	Runtime error	1307 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
6	Runtime error	1887 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
7	Runtime error	1443 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Runtime error	1138 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Runtime error	1676 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Runtime error	966 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
11	Runtime error	1364 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
12	Runtime error	2306 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Runtime error	1711 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	1943 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Runtime error	1201 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Runtime error	1160 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	1091 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)