oj.uz

답안 #295931

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295931 2020-09-10T06:20:05 Z Hemimor Regions (IOI09_regions) C++14
55 / 100
 6424 ms 131076 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=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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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)