oj.uz

답안 #295921

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295921 2020-09-10T06:14:53 Z Hemimor Regions (IOI09_regions) C++14
30 / 100
 5140 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=200;
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 3 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 9 ms 384 KB Output is correct
6 Correct 28 ms 1792 KB Output is correct
7 Correct 32 ms 632 KB Output is correct
8 Correct 36 ms 632 KB Output is correct
9 Correct 78 ms 4636 KB Output is correct
10 Correct 235 ms 9748 KB Output is correct
11 Correct 202 ms 3960 KB Output is correct
12 Correct 410 ms 12280 KB Output is correct
13 Correct 360 ms 7304 KB Output is correct
14 Correct 434 ms 3600 KB Output is correct
15 Correct 668 ms 7964 KB Output is correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3260 ms 9304 KB Output is correct
2 Correct 2730 ms 9448 KB Output is correct
3 Correct 5140 ms 15032 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 1188 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 1905 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 1501 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 1112 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 1716 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 953 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 1456 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 2405 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 1704 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 1909 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 1093 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 1034 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)