oj.uz

Submission #376085

# Submission time Handle Problem Language Result Execution time Memory
376085 2021-03-10T20:35:39 Z eulerdesoja Love Polygon (BOI18_polygon) C++14
29 / 100
 332 ms 31596 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;

#define ll long long
#define pb push_back
#define sz(x) int(x.size())

typedef pair<int,int>ii;
typedef vector<int> vi;

void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0); 
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str(),"w",stdout);
}
const int mxn=1e5+5;
int n,dp[mxn][2],root[mxn];
map<string,int>mp;
string love[mxn][2];
vi g[mxn];
bool v[mxn];

void dfs(int i,int p){
	int sum=0;
	int ma=0;
	for(int j:g[i])if(j!=p){
		dfs(j,i);
		sum+=dp[j][0];
		ma=max(ma,dp[j][1]-dp[j][0]);
	}
	dp[i][1]=1+sum;
	dp[i][0]=ma+sum;
}
int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	//setIO("sort");
	cin>>n;
	if(n&1){
		cout<<-1<<"\n";
		return 0;
	}
	for(int i=0;i<n;i++){
		cin>>love[i][0]>>love[i][1];
		mp[love[i][0]];
		mp[love[i][1]];
	}
	int T=0;
	for(auto it=mp.begin();it!=mp.end();it++){
		T++;
		it->second=T;
	}
	for(int i=0;i<n;i++){
		int x=mp[love[i][0]];
		int y=mp[love[i][1]];
		if(x==y){
			root[x]=1;
			continue;
		}
		g[y].pb(x);

	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(root[i]){
			//self-loop
			dfs(i,0);
			ans+=dp[i][0];
		}
	}
	cout<<n-ans<<"\n";

	return 0;
}

Compilation message

polygon.cpp: In function 'void setIO(std::string)':
polygon.cpp:14:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   14 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
polygon.cpp:15:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   15 |   freopen((s+".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8940 KB Output is correct
2 Correct 7 ms 8940 KB Output is correct
3 Correct 6 ms 8940 KB Output is correct
4 Incorrect 6 ms 8940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8940 KB Output is correct
2 Incorrect 7 ms 8940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 22508 KB Output is correct
2 Correct 328 ms 24396 KB Output is correct
3 Correct 208 ms 20204 KB Output is correct
4 Correct 6 ms 8940 KB Output is correct
5 Correct 332 ms 31596 KB Output is correct
6 Correct 327 ms 21356 KB Output is correct
7 Correct 310 ms 21740 KB Output is correct
8 Correct 262 ms 21356 KB Output is correct
9 Correct 272 ms 20844 KB Output is correct
10 Correct 203 ms 20332 KB Output is correct
11 Correct 6 ms 8940 KB Output is correct
12 Correct 6 ms 8940 KB Output is correct
13 Correct 6 ms 8940 KB Output is correct
14 Correct 6 ms 8940 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8940 KB Output is correct
2 Correct 7 ms 8940 KB Output is correct
3 Correct 6 ms 8940 KB Output is correct
4 Incorrect 6 ms 8940 KB Output isn't correct
5 Halted 0 ms 0 KB -