oj.uz

답안 #613719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
613719 2022-07-30T09:44:44 Z Red_Inside 분수 공원 (IOI21_parks) C++17
5 / 100
 542 ms 101140 KB 
#include "parks.h"
//
#include <bits/stdc++.h>

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

using namespace std;
const int maxn=2e5+100,LOG=17,mod=1e9+7;
int block = 226, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bt(i) (1 << (i))
//#define int ll
const int inf=2e9;
#define y1 yy
#define prev pre
#define pii pair <int, int>

int used[maxn], mt[maxn], to[maxn][3];
vector <int> edge[maxn];
map <int, int> mapp[maxn];
vector <pii> vec, edges;

void dfs(int v)
{
	used[v] = 1;
	shuffle(all(edge[v]), rng);
	for(auto to : edge[v])
	{
		if(!used[to])
		{
			edges.pb({v, to});
			dfs(to);
		}
	}
}

int try_kuhn(int v)
{
	if(used[v] == timer) return 0;
	used[v] = timer;
	if(mt[to[v][0]] == -1)
	{
		mt[to[v][0]] = v;
		return 1;
	}
	if(mt[to[v][1]] == -1)
	{
		mt[to[v][1]] = v;
		return 1;
	}
	if(try_kuhn(mt[to[v][0]]))
	{
		mt[to[v][0]] = v;
		return 1;
	}
	if(try_kuhn(mt[to[v][1]]))
	{
		mt[to[v][1]] = v;
		return 1;
	}
	return 0;
}

int construct_roads(vector <int> x, vector <int> y)
{
	int n = x.size();
	forn(0, i, n-1)
	{
		mapp[x[i]][y[i]] = i;
	}
	forn(0, i, n-1)
	{
		if(mapp[x[i]].count(y[i] - 2))
		{
			edge[i].pb(mapp[x[i]][y[i]-2]);
		}
		if(mapp[x[i]].count(y[i] + 2))
		{
			edge[i].pb(mapp[x[i]][y[i]+2]);
		}
		if(mapp[x[i]+2].count(y[i]))
		{
			edge[i].pb(mapp[x[i]+2][y[i]]);
		}
		if(mapp[x[i]-2].count(y[i]))
		{
			edge[i].pb(mapp[x[i]-2][y[i]]);
		}
	}
	int start = 0;
	forn(1, i, n-1)
	{
		if(x[i] < x[start]) start = i;
		else if(x[i] == x[start] && y[i] > y[start]) start = i;
	}
	dfs(start);
	forn(0, i, n-1)
	{
		if(!used[i]) return 0;
	}
	for(auto i : edges)
	{
		if(y[i.f] == y[i.s])
		{
			vec.pb({max(x[i.f], x[i.s])-1, y[i.f] - 1});
			vec.pb({max(x[i.f], x[i.s])-1, y[i.f] + 1});
		}
		else
		{
			vec.pb({x[i.f] - 1, max(y[i.f], y[i.s]) - 1});
			vec.pb({x[i.f] + 1, max(y[i.f], y[i.s]) - 1});
		}
	}
	sort(all(vec));
	vec.erase(unique(all(vec)), vec.end());
//	FOR(0, i, vec.size()) cout << vec[i].f << "   " << vec[i].s << endl;
	FOR(0, it, edges.size())
	{
		pii i = edges[it];
		if(y[i.f] == y[i.s])
		{
			to[it][0] = lower_bound(all(vec), mp(max(x[i.f], x[i.s])-1, y[i.f] - 1))-vec.begin();
			to[it][1] = lower_bound(all(vec), mp(max(x[i.f], x[i.s])-1, y[i.f] + 1))-vec.begin();
		}
		else
		{
			to[it][0] = lower_bound(all(vec), mp(x[i.f] - 1, max(y[i.f], y[i.s]) - 1))-vec.begin();
			to[it][1] = lower_bound(all(vec), mp(x[i.f] + 1, max(y[i.f], y[i.s]) - 1))-vec.begin();
		}
//		cout << "E " << edges[it].f << " " << edges[it].s << " " << to[it][0] << " " << to[it][1] << endl;
	}
	FOR(0, i, vec.size()) mt[i] = -1;
	
	FOR(0, j, edges.size()) used[j] = 0;
	FOR(0, i, edges.size())
	{
		++timer;
		try_kuhn(i);
	}
	/*while(true)
	{
		cout << "GO\n";
		int ok = 0;
		FOR(0, i, edges.size()) used[i] = 0;
		FOR(0, i, edges.size())
		{
			if(used[i]) continue;
			if(try_kuhn(i))
			{
				ok = 1;
			}
		}
		if(!ok) break;
	}*/
	vector <int> ans1, ans2, ans3, ans4;
	for(auto i : edges)
	{
		ans1.pb(i.f);
		ans2.pb(i.s);
	}
	ans3.assign(edges.size(), 0);
	ans4.assign(edges.size(), 0);
	FOR(0, i, vec.size())
	{
		if(mt[i] == -1) continue;
		ans3[mt[i]] = vec[i].f;
		ans4[mt[i]] = vec[i].s;
	}
	build(ans1, ans2, ans3, ans4);
	return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
  131 |  FOR(0, it, edges.size())
      |         ~~~~~~~~~~~~~~~~               
parks.cpp:131:2: note: in expansion of macro 'FOR'
  131 |  FOR(0, it, edges.size())
      |  ^~~
parks.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
  146 |  FOR(0, i, vec.size()) mt[i] = -1;
      |         ~~~~~~~~~~~~~                  
parks.cpp:146:2: note: in expansion of macro 'FOR'
  146 |  FOR(0, i, vec.size()) mt[i] = -1;
      |  ^~~
parks.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
  148 |  FOR(0, j, edges.size()) used[j] = 0;
      |         ~~~~~~~~~~~~~~~                
parks.cpp:148:2: note: in expansion of macro 'FOR'
  148 |  FOR(0, j, edges.size()) used[j] = 0;
      |  ^~~
parks.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
  149 |  FOR(0, i, edges.size())
      |         ~~~~~~~~~~~~~~~                
parks.cpp:149:2: note: in expansion of macro 'FOR'
  149 |  FOR(0, i, edges.size())
      |  ^~~
parks.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
  177 |  FOR(0, i, vec.size())
      |         ~~~~~~~~~~~~~                  
parks.cpp:177:2: note: in expansion of macro 'FOR'
  177 |  FOR(0, i, vec.size())
      |  ^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 11 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14336 KB Output is correct
6 Correct 9 ms 14332 KB Output is correct
7 Correct 9 ms 14404 KB Output is correct
8 Correct 8 ms 14292 KB Output is correct
9 Correct 203 ms 43568 KB Output is correct
10 Correct 19 ms 17364 KB Output is correct
11 Correct 73 ms 29848 KB Output is correct
12 Correct 26 ms 18812 KB Output is correct
13 Correct 36 ms 20280 KB Output is correct
14 Correct 9 ms 14548 KB Output is correct
15 Correct 11 ms 14664 KB Output is correct
16 Correct 183 ms 43536 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 11 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14336 KB Output is correct
6 Correct 9 ms 14332 KB Output is correct
7 Correct 9 ms 14404 KB Output is correct
8 Correct 8 ms 14292 KB Output is correct
9 Correct 203 ms 43568 KB Output is correct
10 Correct 19 ms 17364 KB Output is correct
11 Correct 73 ms 29848 KB Output is correct
12 Correct 26 ms 18812 KB Output is correct
13 Correct 36 ms 20280 KB Output is correct
14 Correct 9 ms 14548 KB Output is correct
15 Correct 11 ms 14664 KB Output is correct
16 Correct 183 ms 43536 KB Output is correct
17 Correct 7 ms 14420 KB Output is correct
18 Correct 8 ms 14412 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 9 ms 14404 KB Output is correct
21 Correct 8 ms 14292 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Incorrect 542 ms 67828 KB Tree (a[3], b[3]) = (5, 67245) is not adjacent to edge between u[3]=164540 @(4, 199996) and v[3]=6202 @(4, 199994)
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 11 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14336 KB Output is correct
6 Correct 9 ms 14332 KB Output is correct
7 Correct 9 ms 14404 KB Output is correct
8 Correct 8 ms 14292 KB Output is correct
9 Correct 203 ms 43568 KB Output is correct
10 Correct 19 ms 17364 KB Output is correct
11 Correct 73 ms 29848 KB Output is correct
12 Correct 26 ms 18812 KB Output is correct
13 Correct 36 ms 20280 KB Output is correct
14 Correct 9 ms 14548 KB Output is correct
15 Correct 11 ms 14664 KB Output is correct
16 Correct 183 ms 43536 KB Output is correct
17 Correct 7 ms 14420 KB Output is correct
18 Correct 8 ms 14412 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 9 ms 14404 KB Output is correct
21 Correct 8 ms 14292 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Incorrect 542 ms 67828 KB Tree (a[3], b[3]) = (5, 67245) is not adjacent to edge between u[3]=164540 @(4, 199996) and v[3]=6202 @(4, 199994)
24 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 11 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14336 KB Output is correct
6 Correct 9 ms 14332 KB Output is correct
7 Correct 9 ms 14404 KB Output is correct
8 Correct 8 ms 14292 KB Output is correct
9 Correct 203 ms 43568 KB Output is correct
10 Correct 19 ms 17364 KB Output is correct
11 Correct 73 ms 29848 KB Output is correct
12 Correct 26 ms 18812 KB Output is correct
13 Correct 36 ms 20280 KB Output is correct
14 Correct 9 ms 14548 KB Output is correct
15 Correct 11 ms 14664 KB Output is correct
16 Correct 183 ms 43536 KB Output is correct
17 Correct 11 ms 14420 KB Output is correct
18 Correct 9 ms 14428 KB Output is correct
19 Correct 8 ms 14292 KB Output is correct
20 Correct 346 ms 73472 KB Output is correct
21 Correct 384 ms 65292 KB Output is correct
22 Correct 376 ms 73032 KB Output is correct
23 Runtime error 301 ms 101140 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 11 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14336 KB Output is correct
6 Correct 9 ms 14332 KB Output is correct
7 Correct 9 ms 14404 KB Output is correct
8 Correct 8 ms 14292 KB Output is correct
9 Correct 203 ms 43568 KB Output is correct
10 Correct 19 ms 17364 KB Output is correct
11 Correct 73 ms 29848 KB Output is correct
12 Correct 26 ms 18812 KB Output is correct
13 Correct 36 ms 20280 KB Output is correct
14 Correct 9 ms 14548 KB Output is correct
15 Correct 11 ms 14664 KB Output is correct
16 Correct 183 ms 43536 KB Output is correct
17 Incorrect 396 ms 72776 KB Tree (a[25028], b[25028]) = (62569, 100001) is not adjacent to edge between u[25028]=28205 @(50058, 100002) and v[25028]=116919 @(50060, 100002)
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 11 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14336 KB Output is correct
6 Correct 9 ms 14332 KB Output is correct
7 Correct 9 ms 14404 KB Output is correct
8 Correct 8 ms 14292 KB Output is correct
9 Correct 203 ms 43568 KB Output is correct
10 Correct 19 ms 17364 KB Output is correct
11 Correct 73 ms 29848 KB Output is correct
12 Correct 26 ms 18812 KB Output is correct
13 Correct 36 ms 20280 KB Output is correct
14 Correct 9 ms 14548 KB Output is correct
15 Correct 11 ms 14664 KB Output is correct
16 Correct 183 ms 43536 KB Output is correct
17 Correct 7 ms 14420 KB Output is correct
18 Correct 8 ms 14412 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 9 ms 14404 KB Output is correct
21 Correct 8 ms 14292 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Incorrect 542 ms 67828 KB Tree (a[3], b[3]) = (5, 67245) is not adjacent to edge between u[3]=164540 @(4, 199996) and v[3]=6202 @(4, 199994)
24 Halted 0 ms 0 KB -