oj.uz

답안 #125667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125667 2019-07-06T07:47:21 Z faustaadp 사다리꼴 (balkan11_trapezoid) C++17
22 / 100
 299 ms 65540 KB 
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
int n,i,ta,tb,tc,td,j,h1,h2,d[101010],d2[101010],mo=30013;
vector<int> v[101010];
pair<pair<int,int>,pair<int,int> > A[101010];
int depe(int aa)
{
	if(d[aa]==-1)
	{
		d[aa]=0;
		int ii;
		for(ii=0;ii<v[aa].size();ii++)
			d[aa]=max(d[aa],depe(v[aa][ii]));
		d[aa]++;
	}
	return d[aa];
}
ll depe2(ll aa)
{
	if(depe(aa)==1)return 1;
	if(d2[aa]==-1)
	{
		d2[aa]=0;
		int ii;
		for(ii=0;ii<v[aa].size();ii++)
			if(depe(aa)==depe(v[aa][ii])+1)
				d2[aa]=(d2[aa]+depe2(v[aa][ii]))%mo;
	}
	return d2[aa];
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>ta>>tb>>tc>>td;
		A[i]=mp(mp(ta,tb),mp(tc,td));
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(A[i].fi.se<A[j].fi.fi&&A[i].se.se<A[j].se.fi)
				v[i].pb(j);
	memset(d,-1,sizeof(d));
	memset(d2,-1,sizeof(d2));
	for(i=1;i<=n;i++)
		h1=max(h1,depe(i));
	for(i=1;i<=n;i++)
		if(depe(i)==h1)
			h2+=depe2(i);
	cout<<h1<<" "<<h2<<"\n";	
}

Compilation message

trapezoid.cpp: In function 'int depe(int)':
trapezoid.cpp:17:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ii=0;ii<v[aa].size();ii++)
            ~~^~~~~~~~~~~~~
trapezoid.cpp: In function 'll depe2(ll)':
trapezoid.cpp:30:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ii=0;ii<v[aa].size();ii++)
            ~~^~~~~~~~~~~~~

Subtask #1
22.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Partially correct 8 ms 4088 KB Partially correct
4 Partially correct 17 ms 6008 KB Partially correct
5 Partially correct 42 ms 11640 KB Partially correct
6 Partially correct 100 ms 23544 KB Partially correct
7 Partially correct 165 ms 40696 KB Partially correct
8 Partially correct 130 ms 15332 KB Partially correct
9 Runtime error 239 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 215 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 214 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 250 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 251 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 246 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 264 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 268 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 299 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 274 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 291 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 288 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)