Submission #295942

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
295942	2020-09-10T06:26:34 Z	Hemimor	Regions (IOI09_regions)	C++14	60 / 100	7382 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=15000;
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	3 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	9 ms	424 KB	Output is correct
6	Correct	14 ms	544 KB	Output is correct
7	Correct	36 ms	632 KB	Output is correct
8	Correct	25 ms	744 KB	Output is correct
9	Correct	55 ms	1252 KB	Output is correct
10	Correct	129 ms	1744 KB	Output is correct
11	Correct	192 ms	2244 KB	Output is correct
12	Correct	254 ms	3072 KB	Output is correct
13	Correct	358 ms	2968 KB	Output is correct
14	Correct	528 ms	3624 KB	Output is correct
15	Correct	979 ms	6208 KB	Output is correct

Subtask #2

45.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3317 ms	9176 KB	Output is correct
2	Correct	3114 ms	8360 KB	Output is correct
3	Correct	6317 ms	13636 KB	Output is correct
4	Correct	515 ms	4552 KB	Output is correct
5	Correct	698 ms	6852 KB	Output is correct
6	Correct	949 ms	6976 KB	Output is correct
7	Correct	1087 ms	8364 KB	Output is correct
8	Correct	4439 ms	15784 KB	Output is correct
9	Correct	7382 ms	23344 KB	Output is correct
10	Runtime error	901 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
11	Runtime error	1333 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
12	Runtime error	2268 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Runtime error	1691 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	1827 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Runtime error	1095 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Runtime error	1118 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	953 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)