oj.uz

답안 #295924

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295924 2020-09-10T06:17:06 Z Hemimor Regions (IOI09_regions) C++14
30 / 100
 6050 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=400;
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 2 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 11 ms 384 KB Output is correct
6 Correct 22 ms 512 KB Output is correct
7 Correct 40 ms 632 KB Output is correct
8 Correct 39 ms 632 KB Output is correct
9 Correct 69 ms 1272 KB Output is correct
10 Correct 121 ms 2296 KB Output is correct
11 Correct 197 ms 2168 KB Output is correct
12 Correct 267 ms 5112 KB Output is correct
13 Correct 287 ms 2952 KB Output is correct
14 Correct 485 ms 3576 KB Output is correct
15 Correct 869 ms 6328 KB Output is correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3345 ms 9248 KB Output is correct
2 Correct 3150 ms 8436 KB Output is correct
3 Correct 6050 ms 13608 KB Output is correct
4 Runtime error 1793 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 1307 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 1887 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 1138 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 1676 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 966 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 1364 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 2306 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 1711 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 1943 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 1201 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 1160 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 1091 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)