답안 #447037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447037	2021-07-24T09:35:35 Z	fhvirus	Building Skyscrapers (CEOI19_skyscrapers)	C++17	8 / 100	309 ms	16016 KB

skyscrapers

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;} 
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#pragma GCC optimize("Ofast")
#define debug(...) ((void)0)
#endif

// consider doing reverse
// pluck the biggest and reachable out
// then update the neighbor to touched and reachable
// priority queue maintain valid points
// reach: can be reached from outside
// touch: has a neighbor plucked

struct DSU {
	int n, s; vector<int> f;
	DSU(int n = 0) : n(n), s(n), f(n+1) { iota(AI(f), 0); }
	int F(int a){ return a == f[a] ? a : f[a] = F(f[a]); }
	int M(int a, int b){
		a = F(a), b = F(b);
		if(a == b) return false;
		f[b] = a; --s; return true;
	}
	int operator() (int a){ return F(a); }
};
struct LISAN : vector<int> {
	void done() { sort(AI()); erase(unique(AI()), end()); }
	int operator() (int a) { return lower_bound(AI(), a) - begin(); }
};

const int kN = 150051;
const int INF = 1e9 + 7;

const array<pii, 4> d4 = {pii(1, 0), pii(-1, 0), pii(0, 1), pii(0, -1)};
const array<pii, 8> d8 = {pii(1, 1), pii(1, 0), pii(1,-1), pii(0, 1), 
													pii(0, -1), pii(-1, 1), pii(-1, 0), pii(-1, -1)};

int n, t;
pii a[kN];
map<pii, int> mp;
vector<int> adj[kN], bdj[kN];

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> t;
	DSU dsu(n);

	for(int r, c, i = 1; i <= n; ++i){
		cin >> r >> c;
		a[i] = pii(r, c);
		mp[pii(r, c)] = i;
	}

	for(int i = 1; i <= n; ++i){
		auto [r, c] = a[i];
		for(auto [dr, dc]: d8){
			pii u(r + dr, c + dc);
			if(mp.count(u)){
				int v = mp[u];
				if(dsu.M(i, v)){
					adj[i].pb(v);
					adj[v].pb(i);
				}
			}
		}
	}

	for(int i = 1; i <= n; ++i) debug(i, adj[i]);

	if(dsu.s != 1){ cout << "NO"; return 0; }
	cout << "YES\n";

	vector<int> vis(n+1, 0);
	queue<int> q; q.push(1); vis[1] = 1;
	while(!q.empty()){
		int u = q.front(); q.pop();
		cout << u << ' ';
		for(int v: adj[u]) if(!vis[v])
			q.push(v), vis[v] = 1;
	}

	return 0;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	7244 KB	ans=YES N=1
2	Correct	5 ms	7372 KB	ans=YES N=4
3	Correct	5 ms	7372 KB	ans=NO N=4
4	Correct	5 ms	7244 KB	ans=YES N=5
5	Correct	5 ms	7244 KB	ans=YES N=9
6	Correct	5 ms	7244 KB	ans=YES N=5
7	Correct	5 ms	7244 KB	ans=NO N=9
8	Correct	5 ms	7372 KB	ans=NO N=10
9	Correct	5 ms	7296 KB	ans=YES N=10
10	Correct	5 ms	7372 KB	ans=YES N=10
11	Correct	5 ms	7244 KB	ans=YES N=10
12	Correct	5 ms	7244 KB	ans=YES N=9
13	Correct	5 ms	7372 KB	ans=YES N=9
14	Correct	5 ms	7372 KB	ans=YES N=8
15	Correct	6 ms	7368 KB	ans=YES N=8
16	Correct	5 ms	7244 KB	ans=NO N=2

Subtask #2
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	7244 KB	ans=YES N=1
2	Correct	5 ms	7372 KB	ans=YES N=4
3	Correct	5 ms	7372 KB	ans=NO N=4
4	Correct	5 ms	7244 KB	ans=YES N=5
5	Correct	5 ms	7244 KB	ans=YES N=9
6	Correct	5 ms	7244 KB	ans=YES N=5
7	Correct	5 ms	7244 KB	ans=NO N=9
8	Correct	5 ms	7372 KB	ans=NO N=10
9	Correct	5 ms	7296 KB	ans=YES N=10
10	Correct	5 ms	7372 KB	ans=YES N=10
11	Correct	5 ms	7244 KB	ans=YES N=10
12	Correct	5 ms	7244 KB	ans=YES N=9
13	Correct	5 ms	7372 KB	ans=YES N=9
14	Correct	5 ms	7372 KB	ans=YES N=8
15	Correct	6 ms	7368 KB	ans=YES N=8
16	Correct	5 ms	7244 KB	ans=NO N=2
17	Correct	5 ms	7244 KB	ans=YES N=17
18	Correct	6 ms	7372 KB	ans=YES N=25
19	Incorrect	6 ms	7372 KB	Added cell 97 (-3,0) not reachable from infinity
20	Halted	0 ms	0 KB	-

Subtask #3
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	7244 KB	ans=YES N=1
2	Correct	5 ms	7372 KB	ans=YES N=4
3	Correct	5 ms	7372 KB	ans=NO N=4
4	Correct	5 ms	7244 KB	ans=YES N=5
5	Correct	5 ms	7244 KB	ans=YES N=9
6	Correct	5 ms	7244 KB	ans=YES N=5
7	Correct	5 ms	7244 KB	ans=NO N=9
8	Correct	5 ms	7372 KB	ans=NO N=10
9	Correct	5 ms	7296 KB	ans=YES N=10
10	Correct	5 ms	7372 KB	ans=YES N=10
11	Correct	5 ms	7244 KB	ans=YES N=10
12	Correct	5 ms	7244 KB	ans=YES N=9
13	Correct	5 ms	7372 KB	ans=YES N=9
14	Correct	5 ms	7372 KB	ans=YES N=8
15	Correct	6 ms	7368 KB	ans=YES N=8
16	Correct	5 ms	7244 KB	ans=NO N=2
17	Correct	5 ms	7244 KB	ans=YES N=17
18	Correct	6 ms	7372 KB	ans=YES N=25
19	Incorrect	6 ms	7372 KB	Added cell 97 (-3,0) not reachable from infinity
20	Halted	0 ms	0 KB	-

Subtask #4
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	7500 KB	ans=NO N=1934
2	Correct	9 ms	7500 KB	ans=NO N=1965
3	Incorrect	8 ms	7500 KB	Added cell 1824 (339,220) not reachable from infinity
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	7244 KB	ans=YES N=1
2	Correct	5 ms	7372 KB	ans=YES N=4
3	Correct	5 ms	7372 KB	ans=NO N=4
4	Correct	5 ms	7244 KB	ans=YES N=5
5	Correct	5 ms	7244 KB	ans=YES N=9
6	Correct	5 ms	7244 KB	ans=YES N=5
7	Correct	5 ms	7244 KB	ans=NO N=9
8	Correct	5 ms	7372 KB	ans=NO N=10
9	Correct	5 ms	7296 KB	ans=YES N=10
10	Correct	5 ms	7372 KB	ans=YES N=10
11	Correct	5 ms	7244 KB	ans=YES N=10
12	Correct	5 ms	7244 KB	ans=YES N=9
13	Correct	5 ms	7372 KB	ans=YES N=9
14	Correct	5 ms	7372 KB	ans=YES N=8
15	Correct	6 ms	7368 KB	ans=YES N=8
16	Correct	5 ms	7244 KB	ans=NO N=2
17	Correct	5 ms	7244 KB	ans=YES N=17
18	Correct	6 ms	7372 KB	ans=YES N=25
19	Incorrect	6 ms	7372 KB	Added cell 97 (-3,0) not reachable from infinity
20	Halted	0 ms	0 KB	-

Subtask #6
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	222 ms	14864 KB	ans=NO N=66151
2	Correct	159 ms	13492 KB	ans=NO N=64333
3	Incorrect	309 ms	16016 KB	Added cell 69316 (-103,-128) not reachable from infinity
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	7500 KB	ans=NO N=1934
2	Correct	9 ms	7500 KB	ans=NO N=1965
3	Incorrect	8 ms	7500 KB	Added cell 1824 (339,220) not reachable from infinity
4	Halted	0 ms	0 KB	-

답안 #447037

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 0 / 14.0

Subtask #3 0 / 12.0

Subtask #4 0 / 17.0

Subtask #5 0 / 20.0

Subtask #6 0 / 10.0

Subtask #7 0 / 19.0

Subtask #1
8.0 / 8.0

Subtask #2
0 / 14.0

Subtask #3
0 / 12.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0

Subtask #6
0 / 10.0

Subtask #7
0 / 19.0