oj.uz

Submission #295969

# Submission time Handle Problem Language Result Execution time Memory
295969 2020-09-10T06:43:34 Z Hemimor Regions (IOI09_regions) C++14
100 / 100
 4725 ms 40548 KB 
#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=25000;
int n,m,q,id=0;
vvi g,b,bl,br;
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=bl=br=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<n;i++){
		bl[a[i]].push_back(lt[i]);
		br[a[i]].push_back(rt[i]);
	}
	for(int i=0;i<m;i++){
		sort(bl[i].begin(),bl[i].end());
		sort(br[i].begin(),br[i].end());
	}
	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;
		scanf("%d%d",&x,&y);
		x--,y--;
		if(mp.find({x,y})!=mp.end()) res=mp[{x,y}];
		else{
			ll tmp=0;
			int I=0,J=0,n1=bl[x].size(),n2=bl[y].size();
			for(int j=0;j<n1;j++){
				while(I<n2&&bl[y][I]<bl[x][j]) I++;
				while(J<n2&&bl[y][J]<br[x][j]) J++;
				tmp+=J-I;
			}
//			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);
			res=tmp;
		}
		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:136:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  136 |   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 18 ms 512 KB Output is correct
7 Correct 42 ms 632 KB Output is correct
8 Correct 46 ms 728 KB Output is correct
9 Correct 72 ms 1376 KB Output is correct
10 Correct 80 ms 1836 KB Output is correct
11 Correct 114 ms 2296 KB Output is correct
12 Correct 165 ms 3320 KB Output is correct
13 Correct 191 ms 3276 KB Output is correct
14 Correct 296 ms 3960 KB Output is correct
15 Correct 292 ms 6636 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1174 ms 10036 KB Output is correct
2 Correct 1403 ms 9200 KB Output is correct
3 Correct 1834 ms 14448 KB Output is correct
4 Correct 338 ms 5240 KB Output is correct
5 Correct 314 ms 7592 KB Output is correct
6 Correct 610 ms 8312 KB Output is correct
7 Correct 899 ms 9816 KB Output is correct
8 Correct 1026 ms 17716 KB Output is correct
9 Correct 1854 ms 26320 KB Output is correct
10 Correct 2322 ms 33540 KB Output is correct
11 Correct 2959 ms 32488 KB Output is correct
12 Correct 2498 ms 25924 KB Output is correct
13 Correct 2799 ms 27864 KB Output is correct
14 Correct 3590 ms 29960 KB Output is correct
15 Correct 4639 ms 36472 KB Output is correct
16 Correct 4725 ms 40548 KB Output is correct
17 Correct 3837 ms 38724 KB Output is correct