36 2021. 01. 08 20:09:20 mraron 2015. szeptember cpp11 Elfogadva 2ms 2128 KiB
#include<bits/stdc++.h>
#include<cstdlib>

using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;

#define all(s) (s).begin(),(s).end()
#define pb push_back
#define IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define INF std::numeric_limits<int>::max()
#define tmax(a,b,c) max((a),max((b),(c)))
#define tmin(a,b,c) min((a),min((b),(c)))
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define mp make_pair

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

int d1[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
int d2[8][2]={{1,0},{0,1},{0,-1},{-1,0},{1,1},{-1,1},{1,-1},{-1,-1}};

//---PROGRAM KEZDETE---

//Egy kör
struct Kor {
	int i,x,y,r; //hanyadik volt a bemenetben, x,y koordináta r sugár
	bool upper; //felső-e?
	bool lower; //alsó-e?
};

//szomszédsági lista a gráfnak
vector<vector<int>> adj(500);
vector<Kor> t;//bemenetről kapott körök

//egy adott felső csúcsból alsót keresünk
bool searchforlower(int i, bool tt[])
{
	if(t[i].lower) return true; //megtaláltuk
	bool ans=false;
	for(int j=0;j<adj[i].size();++j) //szomszédjai
	{
		if(!tt[adj[i][j]]) //ebben a szomszédban még nem jártunk!
		{
			tt[adj[i][j]]=true; //ne menjünk ide újra...
			ans|=searchforlower(adj[i][j], tt); //rekurzió ebbe a szomszédosba
		}
	}
	return ans;
}



int main()
{
	IO;
	int n,m,k;cin>>n>>m>>k;
	
	//beolvasás
	for(int i=0;i<k;++i)
	{
		int x,y,r;cin>>x>>y>>r;
		Kor tt;
		tt.i=i;tt.x=x;tt.y=y;tt.r=r;tt.upper=false;tt.lower=false;
		t.pb(tt);
	}

	//felső és alsó körök/csúcsok meghatározása
	for(int j=0;j<t.size();++j)
	{
		if(t[j].y-t[j].r<=0) t[j].upper=true;
		if(t[j].y+t[j].r>=m) t[j].lower=true;
	}
	
	//mely körök/csúcsok között található él
	for(int i=0;i<k;++i)
	{
		for(int j=i+1;j<k;++j)
		{
			double dist = ((t[i].x-t[j].x)*(t[i].x-t[j].x))+((t[i].y-t[j].y)*(t[i].y-t[j].y)); //(középpontok távolsága)^2
			double maxdist = (t[i].r+t[j].r)*(t[i].r+t[j].r); //(élek távolsága)^2
			if(dist<=maxdist) //van él
			{
				adj[i].pb(j);
				adj[j].pb(i);
			}
		}
	}
	
	bool tt[105]; //jártunk már-e a csúcsban
	for(int j=0;j<105;++j) tt[j]=false; 
	
	bool vezet=true;
	for(int i=0;i<k&&vezet;++i) //körökön végig megyünk...
	{
		if(t[i].upper && !tt[i]) //akkor keresünk kapcsolatot alsó csúccsal, ha felső csúcsnál vagyunk és még nem jártunk ebben a felső csúcsban.
		{
			tt[i]=true; //már jártunk itt...
			if(searchforlower(i, tt)) vezet=false; //ha találunk utat: "nem vezet"
		}
		
	}
	
	cout<<(vezet?"Vezet":"Nem vezet")<<"\n";
	return 0;
}

1 - Elfogadva
Memória: 1836KiB
Idő: 2ms

Program kimenete:
Vezet
Elvárt kimenet:
Vezet
Ellenőrző kimenet:
ok "Vezet"

2 - Elfogadva
Memória: 1864KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

3 - Elfogadva
Memória: 1932KiB
Idő: 1ms

Program kimenete:
Vezet
Elvárt kimenet:
Vezet
Ellenőrző kimenet:
ok "Vezet"

4 - Elfogadva
Memória: 1972KiB
Idő: 1ms

Program kimenete:
Vezet
Elvárt kimenet:
Vezet
Ellenőrző kimenet:
ok "Vezet"

5 - Elfogadva
Memória: 1936KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

6 - Elfogadva
Memória: 1972KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

7 - Elfogadva
Memória: 1948KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

8 - Elfogadva
Memória: 2004KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

9 - Elfogadva
Memória: 1972KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

10 - Elfogadva
Memória: 1952KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

11 - Elfogadva
Memória: 1952KiB
Idő: 1ms

Program kimenete:
Vezet
Elvárt kimenet:
Vezet
Ellenőrző kimenet:
ok "Vezet"

12 - Elfogadva
Memória: 2000KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

13 - Elfogadva
Memória: 1972KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

14 - Elfogadva
Memória: 1968KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

15 - Elfogadva
Memória: 1980KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

16 - Elfogadva
Memória: 2040KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

17 - Elfogadva
Memória: 1988KiB
Idő: 1ms

Program kimenete:
Vezet
Elvárt kimenet:
Vezet
Ellenőrző kimenet:
ok "Vezet"

18 - Elfogadva
Memória: 1988KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

19 - Elfogadva
Memória: 2016KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

20 - Elfogadva
Memória: 2016KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

21 - Elfogadva
Memória: 2016KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

22 - Elfogadva
Memória: 2064KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

23 - Elfogadva
Memória: 2096KiB
Idő: 2ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

24 - Elfogadva
Memória: 2112KiB
Idő: 2ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

25 - Elfogadva
Memória: 2112KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

26 - Elfogadva
Memória: 2084KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

27 - Elfogadva
Memória: 2128KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

28 - Elfogadva
Memória: 2088KiB
Idő: 2ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

29 - Elfogadva
Memória: 2028KiB
Idő: 1ms

Program kimenete:
Vezet
Elvárt kimenet:
Vezet
Ellenőrző kimenet:
ok "Vezet"

30 - Elfogadva
Memória: 2028KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

31 - Elfogadva
Memória: 2036KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

32 - Elfogadva
Memória: 2072KiB
Idő: 1ms

Program kimenete:
Vezet
Elvárt kimenet:
Vezet
Ellenőrző kimenet:
ok "Vezet"

33 - Elfogadva
Memória: 2068KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

34 - Elfogadva
Memória: 2080KiB
Idő: 1ms

Program kimenete:
Vezet
Elvárt kimenet:
Vezet
Ellenőrző kimenet:
ok "Vezet"

35 - Elfogadva
Memória: 2076KiB
Idő: 1ms

Program kimenete:
Vezet
Elvárt kimenet:
Vezet
Ellenőrző kimenet:
ok "Vezet"

36 - Elfogadva
Memória: 2052KiB
Idő: 1ms

Program kimenete:
Nem vezet
Elvárt kimenet:
Nem vezet
Ellenőrző kimenet:
ok 2 tokens

37 - Elfogadva
Memória: 2084KiB
Idő: 1ms

Program kimenete:
Vezet
Elvárt kimenet:
Vezet
Ellenőrző kimenet:
ok "Vezet"