oj.uz

답안 #295942

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295942 2020-09-10T06:26:34 Z Hemimor Regions (IOI09_regions) C++14
60 / 100
 7382 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=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

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

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