oj.uz

답안 #731649

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
731649 2023-04-27T17:49:53 Z shadow_sami Love Polygon (BOI18_polygon) C++17
29 / 100
 2000 ms 26860 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define fip(a,b) for(ll i = a; i < b ; i++)
#define fjp(a,b) for(ll j = a; j < b ; j++)
#define fp(k,a,b) for(ll k = a; k < b ; k++)
#define fin(a,b) for(ll i = a; i >= b ; i--)
#define fjn(a,b) for(ll i = a; j >= b ; j--)
#define fn(k,a,b) for(ll k = a; k >= b ; k--)
#define fx(a) for(auto x : a)
#define ordered_set tree<pi,null_type,less<pi>,rb_tree_tag,tree_order_statistics_node_update>
#define total_one(k) __builtin_popcount(k)
#define back_zero(k) __builtin_ctzll(k)
#define front_zero(k) __builtin_clzll(k)
#define nli "\n"

ll n,m,ans,sum,res,cnt,tptp,tp,tp2;

const ll mx = 1e5 + 5;
const ll mod = 1e9 + 7;

unordered_map<string,ll> hashe;
string k1,k2;
vi adj[mx];
vi reverse_adj[mx];
bool vis[mx];

ll find_root(ll k){
	if(adj[k].front() == k)
		return k;
	fx(adj[k])
		return find_root(x);
}

ll dfs(ll u,ll root){
	vis[u] = 1;
	ll sz = 1;
	fx(reverse_adj[u])
		if(!vis[x]){
			sz += dfs(x,root);
		}
	if(sz>=2){
		ans += sz - 1;
		sz = 0;
	}
	if(sz==1 && u == root){
		ans++;
	}
	return sz;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	// #ifdef code
		// freopen("input1.txt","r",stdin);
		// freopen("output1.txt","w",stdout);
		// freopen("error1.txt","w",stderr);
	// #endif

		cin>>n;
		tptp = 0;
		ans = 0;
		cnt = 0;
		fip(1,n+1){
			cin>>k1>>k2;
			if(!hashe.count(k1)){
				cnt++;
				hashe[k1] = cnt;
			}				
			if(!hashe.count(k2)){
				cnt++;
				hashe[k2] = cnt;
			}				
			adj[hashe[k1]].push_back(hashe[k2]);
			reverse_adj[hashe[k2]].push_back(hashe[k1]);
		}
		if(n&1){
			cout<<-1<<nli;
			return 0;
		}
		fip(1,n+1){
			if(!vis[i]){
				tptp = find_root(i);
				dfs(tptp,tptp);
			}
		}
		cout<<ans<<nli;

	// cerr << "Time elapsed : " << setprecision(6) << 100.00 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message

polygon.cpp: In function 'll find_root(ll)':
polygon.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
   41 | }
      | ^

Subtask #1
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5032 KB Output is correct
4 Execution timed out 2067 ms 4948 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 2060 ms 4948 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 18468 KB Output is correct
2 Correct 181 ms 21968 KB Output is correct
3 Correct 92 ms 21148 KB Output is correct
4 Correct 109 ms 19688 KB Output is correct
5 Correct 162 ms 26860 KB Output is correct
6 Correct 167 ms 19828 KB Output is correct
7 Correct 129 ms 19800 KB Output is correct
8 Correct 108 ms 20044 KB Output is correct
9 Correct 103 ms 19588 KB Output is correct
10 Correct 78 ms 18764 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 4 ms 5028 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5032 KB Output is correct
4 Execution timed out 2067 ms 4948 KB Time limit exceeded
5 Halted 0 ms 0 KB -