oj.uz

Submission #105706

# Submission time Handle Problem Language Result Execution time Memory
105706 2019-04-14T04:16:43 Z Pro_ktmr 전압 (JOI14_voltage) C++14
100 / 100
 493 ms 33268 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5504 KB Output is correct
2 Correct 10 ms 5248 KB Output is correct
3 Correct 9 ms 5120 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 9 ms 5240 KB Output is correct
6 Correct 11 ms 5368 KB Output is correct
7 Correct 9 ms 5240 KB Output is correct
8 Correct 9 ms 5240 KB Output is correct
9 Correct 9 ms 5248 KB Output is correct
10 Correct 10 ms 5264 KB Output is correct
11 Correct 11 ms 5216 KB Output is correct
12 Correct 6 ms 5248 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 19284 KB Output is correct
2 Correct 244 ms 26160 KB Output is correct
3 Correct 127 ms 19284 KB Output is correct
4 Correct 242 ms 27464 KB Output is correct
5 Correct 28 ms 7160 KB Output is correct
6 Correct 206 ms 23740 KB Output is correct
7 Correct 221 ms 28768 KB Output is correct
8 Correct 214 ms 28788 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 19416 KB Output is correct
2 Correct 152 ms 28732 KB Output is correct
3 Correct 161 ms 28688 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 175 ms 23008 KB Output is correct
6 Correct 270 ms 21620 KB Output is correct
7 Correct 236 ms 25044 KB Output is correct
8 Correct 230 ms 26712 KB Output is correct
9 Correct 204 ms 26080 KB Output is correct
10 Correct 240 ms 24776 KB Output is correct
11 Correct 230 ms 21600 KB Output is correct
12 Correct 219 ms 23784 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 23236 KB Output is correct
2 Correct 255 ms 33268 KB Output is correct
3 Correct 23 ms 10608 KB Output is correct
4 Correct 239 ms 26080 KB Output is correct
5 Correct 222 ms 27092 KB Output is correct
6 Correct 262 ms 26004 KB Output is correct
7 Correct 405 ms 29940 KB Output is correct
8 Correct 390 ms 31328 KB Output is correct
9 Correct 444 ms 29116 KB Output is correct
10 Correct 463 ms 31588 KB Output is correct
11 Correct 411 ms 28756 KB Output is correct
12 Correct 439 ms 31540 KB Output is correct
13 Correct 333 ms 28036 KB Output is correct
14 Correct 398 ms 31840 KB Output is correct
15 Correct 460 ms 31712 KB Output is correct
16 Correct 392 ms 30632 KB Output is correct
17 Correct 493 ms 28288 KB Output is correct
18 Correct 365 ms 27812 KB Output is correct