Submission #105706

#	Time	Username	Problem	Language	Result	Execution time	Memory
105706		Pro_ktmr	전압 (JOI14_voltage)	C++14	100 / 100	493 ms	33268 KiB

voltage

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()

struct SegmentTree{
private:
	int n;
	vector<long long> nodes;
public:
	void init(int N){ //初期化する O(N)
		nodes.clear();
		n = 1;
		while(n < N) n *= 2;
		n = 2 * n -1;
		for(int i=0; i<n; i++) nodes.push_back(LLONG_MAX);
	}
	void update(int i, long long x){ //値を変更する O(log N)
		i += n / 2;
		nodes[i] = x;
		while(i > 0){
			i = (i-1)/2; //親の取得は(i-1)/2
			nodes[i] = min(nodes[i*2+1], nodes[i*2+2]); //子の取得はi*2+1,i*2+2
		}
	}
	long long minimum(int a, int b, int k=0, int l=0, int r=-1){ //[a,b)の最小値を求める O(log N)
		if(r == -1) r = n/2+1;
		if(r <= a || b <= l) return LLONG_MAX; //交差する場合
		if(a <= l && r <= b) return nodes[k]; //完全に含む場合
		long long valueL = minimum(a, b, k*2+1, l, (l+r)/2);
		long long valueR = minimum(a, b, k*2+2, (l+r)/2, r);
		return min(valueL, valueR);
	}
	long long m;
	long long find(int a, int b, int k=0, int l=0, int r=-1){
		if(r == -1){
			m = minimum(a, b);
			r = (n+1)/2;
		}
		if(r <= a || b <= l) return LLONG_MAX; //交差する場合
		if(r-l == 1){
			if(nodes[k] == m) return l;
			else return LLONG_MAX;
		}
		if(a <= l && r <= b){ //完全に含む場合
			long long valueL = minimum(a, b, k*2+1, l, (l+r)/2);
			long long valueR = minimum(a, b, k*2+2, (l+r)/2, r);
			if(valueL <= valueR) return find(a, b, k*2+1, l, (l+r)/2);
			else return find(a, b, k*2+2, (l+r)/2, r);
		}
		long long valueL = find(a, b, k*2+1, l, (l+r)/2);
		long long valueR = find(a, b, k*2+2, (l+r)/2, r);
		return min(valueL, valueR);
	}
};

int N,M;
vector<pair<int,int> > edge;
bool ki[200000] = {};
vector<pair<int,int> > tonari[100000];
bool already[100000] = {};
int dfs_order[100000];

int par[100000];
vector<int> child[100000];
int c = 0;
vector<pair<int,int> > other;
void dfs(int now){
	int next = c-1;
	for(int i=0; i<tonari[now].size(); i++){
		if(already[tonari[now][i].first]) continue;
		already[tonari[now][i].first] = true;
		ki[tonari[now][i].second] = true;
		par[c] = next;
		dfs_order[tonari[now][i].first] = c;
		child[next].push_back(c);
		c++;
		dfs(tonari[now][i].first);
	}
}

int d[100000] = {};
int depth(int i){
	if(par[i] == i) return 0;
	if(d[i] != 0) return d[i];
	return d[i] = 1 + depth(par[i]);
}

vector<int> order;
int pre[100000];
void dfs2(int now){
	pre[now] = order.size();
	order.push_back(now);
	for(int i=0; i<child[now].size(); i++){
		dfs2(child[now][i]);
		order.push_back(now);
	}
}

SegmentTree st;
int lca(int a, int b){
	//cout << a << " " << b << " " << pre[a] << " " << pre[b] << " " << st.minimum(pre[a], pre[b]+1) <<  endl;
	a = pre[a];
	b = pre[b];
	if(a > b) swap(a,b);
	return (int)(st.minimum(a, b+1));
}
int shouldChange[100000] = {};
int notChange[100000] = {};

int ans = 0;
int main(){
	cin >> N >> M;
	for(int i=0; i<M; i++){
		int a,b;
		cin >> a >> b;
		a--; b--;
		tonari[a].push_back(MP(b,i));
		tonari[b].push_back(MP(a,i));
		edge.push_back(MP(a,b));
	}
	
	for(int i=0; i<N; i++){
		if(already[i]) continue;
		already[i] = true;
		par[c] = c;
		dfs_order[i] = c;
		c++;
		dfs(i);
	}

	for(int i=0; i<M; i++){
		if(ki[i]) continue;
		other.push_back(MP(dfs_order[edge[i].first], dfs_order[edge[i].second]));
	}

	//for(int i=0; i<N; i++) cout << par[i] << endl;
	//for(int i=0; i<other.size(); i++) cout << other[i].first << " " << other[i].second << endl;
	//for(int i=0; i<N; i++){
	//	for(int j=0; j<child[i].size(); j++){
	//		cout << child[i][j] << " ";
	//	}
	//	cout << endl;
	//}

	//
	
	int tmp = 0;
	for(int i=0; i<other.size(); i++){
		if(depth(other[i].first)%2 == depth(other[i].second)%2) tmp++;
	}
	if(tmp == 1) ans++;
	//cout << tmp << endl;

	//
	
	for(int i=0; i<N; i++){
		if(par[i] != i) continue;
		dfs2(i);
	}
	//for(int i=0; i<order.size(); i++) cout << order[i] << (i==order.size()-1 ? "\n" : " ");
	st.init(order.size());
	for(int i=0; i<order.size(); i++) st.update(i, order[i]);

	//
	
	int count = 0;
	for(int i=0; i<other.size(); i++){
		//cout << other[i].first << " " << other[i].second << " " << lca(other[i].first, other[i].second) << endl;
		if(depth(other[i].first)%2 == depth(other[i].second)%2){
			count++;
			shouldChange[other[i].first] += 1;
			shouldChange[other[i].second] += 1;
			shouldChange[lca(other[i].first, other[i].second)] -= 2;
		}
		else{
			notChange[other[i].first] += 1;
			notChange[other[i].second] += 1;
			notChange[lca(other[i].first, other[i].second)] -= 2;
		}
	}

	vector<pair<int,int> > d_i;
	for(int i=0; i<N; i++){
		d_i.push_back(MP(depth(i),i));
	}
	sort(d_i.begin(), d_i.end());
	reverse(d_i.begin(), d_i.end());

	for(int i=0; i<N; i++){
		if(par[d_i[i].second] == d_i[i].second) continue;
		shouldChange[par[d_i[i].second]] += shouldChange[d_i[i].second];
		notChange[par[d_i[i].second]] += notChange[d_i[i].second];
	}

	//

	for(int i=0; i<N; i++){
		if(par[i] == i) continue;
		//cout << notChange[i] << " " << shouldChange[i] << endl;
		if(notChange[i] == 0 && shouldChange[i] == count) ans++;
	}

	//

	cout << ans << endl;

	return 0;
}

Compilation message (stderr)

voltage.cpp: In function 'void dfs(int)':
voltage.cpp:73:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<tonari[now].size(); i++){
               ~^~~~~~~~~~~~~~~~~~~
voltage.cpp: In function 'void dfs2(int)':
voltage.cpp:97:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<child[now].size(); i++){
               ~^~~~~~~~~~~~~~~~~~
voltage.cpp: In function 'int main()':
voltage.cpp:152:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<other.size(); i++){
               ~^~~~~~~~~~~~~
voltage.cpp:166:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<order.size(); i++) st.update(i, order[i]);
               ~^~~~~~~~~~~~~
voltage.cpp:171:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<other.size(); i++){
               ~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45