oj.uz

Submission #776519

# Submission time Handle Problem Language Result Execution time Memory
776519 2023-07-08T03:16:23 Z jamielim Dragon 2 (JOI17_dragon2) C++14
0 / 100
 876 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef long long ll;
typedef unsigned long long ull;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const ll MOD=1000000007;

int n,m;
vector<ii> tribe[30005];
vector<int> adj[30005];
int d1,e1,d2,e2;
int q;

double road(int x){
	double m=(double)(e2-e1)/(d2-d1);
	return m*(x-d1)+e1;
}

inline bool ixn(ii p1,ii p2){
	//printf("try %d %d %d %d\n",p1.fi,p1.se,p2.fi,p2.se);
	if(p1.fi==p2.fi){
		//printf("a\n");
		if(d1>p1.fi||d2<p1.fi)return 0;
		// x coordinate is correct
		if(p1.se<p2.se){
			if(p2.se<road(p1.fi))return 1;
		}else{
			if(p2.se>road(p1.fi))return 1;
		}
	}else{
		//printf("b\n");
		double m=(double)(p2.se-p1.se)/(double)(p2.fi-p1.fi);
		if(d1==d2){
			double y=m*(d1-p2.fi)+p2.se;
			if(e1<y&&y<e2)return 1;
		}else{
			if(p1.fi<p2.fi){
				double a=p1.se,b=m*(d2-p2.fi)+p2.se;
				if(p1.fi<d1){
					a=m*(d1-p2.fi)+p2.se;
					if(a<e1&&e2<b)return 1;
					if(a>e1&&e2>b)return 1;
				}else{
					double r=road(p1.fi);
					//printf("%lf %lf %d %lf\n",a,r,e2,b);
					if(a<r&&e2<b)return 1;
					if(a>r&&e2>b)return 1;
				}
			}else{
				double a=m*(d1-p2.fi)+p2.se,b=p1.se;
				if(p1.fi>d2){
					b=m*(d2-p2.fi)+p2.se;
					if(a<e1&&e2<b)return 1;
					if(a>e1&&e2>b)return 1;
				}else{
					double r=road(p1.fi);
					if(a<e1&&r<b)return 1;
					if(a>e1&&r>b)return 1;
				}
			}
		}
	}
	return 0;
}

int main(){
	scanf("%d%d",&n,&m);
	int a,b,c;
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&a,&b,&c);
		tribe[c].pb(a,b);
	}
	scanf("%d%d%d%d",&d1,&e1,&d2,&e2);
	if(d1>d2){
		swap(d1,d2);
		swap(e1,e2);
	}else if(d1==d2){
		if(e1>e2)swap(e1,e2);
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			if(i==j)continue;
			for(ii k:tribe[i]){
				for(ii l:tribe[j]){
					if(ixn(k,l)){
					//	printf("1\n");
						adj[i].pb(j);
					}else{
					//	printf("0\n");
					}
				}
			}
		}
	}
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&a,&b);
		int ans=0;
		for(int i:adj[a]){
			if(i==b)ans++;
		}
		printf("%d\n",ans);
	}
}

Compilation message

dragon2.cpp: In function 'int main()':
dragon2.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
dragon2.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%d%d%d",&a,&b,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
dragon2.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  scanf("%d%d%d%d",&d1,&e1,&d2,&e2);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
dragon2.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 18264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 876 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 18264 KB Output isn't correct
2 Halted 0 ms 0 KB -