Submission #295931

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
295931	2020-09-10T06:20:05 Z	Hemimor	Regions (IOI09_regions)	C++14	55 / 100	6424 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=10000;
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	2 ms	384 KB	Output is correct
4	Correct	6 ms	384 KB	Output is correct
5	Correct	8 ms	384 KB	Output is correct
6	Correct	17 ms	512 KB	Output is correct
7	Correct	22 ms	572 KB	Output is correct
8	Correct	38 ms	632 KB	Output is correct
9	Correct	64 ms	1272 KB	Output is correct
10	Correct	114 ms	1776 KB	Output is correct
11	Correct	186 ms	2296 KB	Output is correct
12	Correct	246 ms	3180 KB	Output is correct
13	Correct	280 ms	2936 KB	Output is correct
14	Correct	435 ms	3652 KB	Output is correct
15	Correct	799 ms	6392 KB	Output is correct

Subtask #2

40.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3087 ms	9248 KB	Output is correct
2	Correct	3058 ms	8420 KB	Output is correct
3	Correct	6424 ms	13332 KB	Output is correct
4	Correct	642 ms	4600 KB	Output is correct
5	Correct	574 ms	6960 KB	Output is correct
6	Correct	1167 ms	7032 KB	Output is correct
7	Correct	1132 ms	8240 KB	Output is correct
8	Correct	4066 ms	16072 KB	Output is correct
9	Runtime error	1583 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Runtime error	924 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
11	Runtime error	1345 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
12	Runtime error	2409 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Runtime error	1709 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	1883 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Runtime error	1151 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Runtime error	1133 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	978 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)