oj.uz

답안 #295929

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295929 2020-09-10T06:18:59 Z Hemimor Regions (IOI09_regions) C++14
30 / 100
 6475 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=2000;
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 376 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 10 ms 384 KB Output is correct
6 Correct 28 ms 512 KB Output is correct
7 Correct 33 ms 632 KB Output is correct
8 Correct 54 ms 632 KB Output is correct
9 Correct 78 ms 1184 KB Output is correct
10 Correct 138 ms 1656 KB Output is correct
11 Correct 210 ms 2168 KB Output is correct
12 Correct 253 ms 2936 KB Output is correct
13 Correct 331 ms 2972 KB Output is correct
14 Correct 511 ms 3672 KB Output is correct
15 Correct 834 ms 6224 KB Output is correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3552 ms 9172 KB Output is correct
2 Correct 2996 ms 8540 KB Output is correct
3 Correct 6475 ms 13228 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 1186 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 1892 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 1110 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 1625 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 968 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 1362 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 2329 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 1642 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 1835 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 1087 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 983 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)