oj.uz

Submission #776570

# Submission time Handle Problem Language Result Execution time Memory
776570 2023-07-08T04:09:28 Z jamielim Dragon 2 (JOI17_dragon2) C++14
0 / 100
 1254 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;
const double EPS=1E-10;

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

inline double road(int x){
	double m=(double)(e2-e1)/(double)(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){
		if(d1>p1.fi||d2<p1.fi)return 0;
		// x coordinate is correct
		if(p1.se<p2.se){
			if(p2.se<road(p1.fi)-EPS)return 1;
		}else{
			if(p2.se>road(p1.fi)-EPS)return 1;
		}
	}else{
		if(d1==d2){
			if(p1.fi<p2.fi&&p2.fi>d1)return 0;
			if(p1.fi>p2.fi&&p2.fi<d1)return 0;
			double m=(double)(p2.se-p1.se)/(double)(p2.fi-p1.fi);
			double y=m*(d1-p2.fi)+p2.se;
			if(e1<y-EPS&&y+EPS<e2)return 1;
		}else{
			double m1=(double)(e2-e1)/(double)(d2-d1);
			double m2=(double)(p2.se-p1.se)/(double)(p2.fi-p1.fi);
			double c1=e1-m1*d1,c2=p1.se-m2*p1.fi;
			if(m1==m2){
				return 0;
			}
			double x=(c1-c2)/(m2-m1);
			if(p1.fi<p2.fi&&p1.fi<x-EPS){
				if(d1<x-EPS&&x+EPS<d2)return 1;
			}else if(p1.fi>p2.fi&&p1.fi>x+EPS){
				if(d1<x-EPS&&x+EPS<d2)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:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
dragon2.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d%d%d",&a,&b,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
dragon2.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  scanf("%d%d%d%d",&d1,&e1,&d2,&e2);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
dragon2.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 11744 KB Output is correct
2 Correct 164 ms 10948 KB Output is correct
3 Correct 274 ms 18668 KB Output is correct
4 Correct 318 ms 10828 KB Output is correct
5 Correct 306 ms 22872 KB Output is correct
6 Incorrect 145 ms 1876 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 1254 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 Correct 85 ms 11744 KB Output is correct
2 Correct 164 ms 10948 KB Output is correct
3 Correct 274 ms 18668 KB Output is correct
4 Correct 318 ms 10828 KB Output is correct
5 Correct 306 ms 22872 KB Output is correct
6 Incorrect 145 ms 1876 KB Output isn't correct
7 Halted 0 ms 0 KB -