Submission #295929

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
295929	2020-09-10T06:18:59 Z	Hemimor	Regions (IOI09_regions)	C++14	30 / 100	6475 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=2000;
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	376 KB	Output is correct
4	Correct	7 ms	384 KB	Output is correct
5	Correct	10 ms	384 KB	Output is correct
6	Correct	28 ms	512 KB	Output is correct
7	Correct	33 ms	632 KB	Output is correct
8	Correct	54 ms	632 KB	Output is correct
9	Correct	78 ms	1184 KB	Output is correct
10	Correct	138 ms	1656 KB	Output is correct
11	Correct	210 ms	2168 KB	Output is correct
12	Correct	253 ms	2936 KB	Output is correct
13	Correct	331 ms	2972 KB	Output is correct
14	Correct	511 ms	3672 KB	Output is correct
15	Correct	834 ms	6224 KB	Output is correct

Subtask #2

15.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3552 ms	9172 KB	Output is correct
2	Correct	2996 ms	8540 KB	Output is correct
3	Correct	6475 ms	13228 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	1186 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
6	Runtime error	1892 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	1110 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Runtime error	1625 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Runtime error	968 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
11	Runtime error	1362 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
12	Runtime error	2329 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Runtime error	1642 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	1835 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	1087 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	983 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)