Submission #199737

#	Time	Username	Problem	Language	Result	Execution time	Memory
199737		arnold518	전압 (JOI14_voltage)	C++14	100 / 100	245 ms	21868 KiB

voltage

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, M, ans;
vector<int> adj[MAXN+10];

bool vis[MAXN+10];
int in[MAXN+10], out[MAXN+10], col[MAXN+10], root[MAXN+10], cnt;

vector<pii> odd, even;

void dfs(int now, int bef, int dep)
{
	vis[now]=true;
	col[now]=dep;
	in[now]=++cnt;

	int p=0;
	for(int nxt : adj[now])
	{
		if(nxt==bef && p==0) { p++; continue; }
		if(!vis[nxt]) dfs(nxt, now, 1-dep);
		else
		{
			if(now<nxt) continue;
			if(col[now]!=col[nxt]) odd.push_back({now, nxt});
			else even.push_back({now, nxt});
		}
	}
	out[now]=cnt;
}

struct BIT
{
	int tree[MAXN+10];
	BIT() { memset(tree, 0, sizeof(tree)); }
	void update(int i) { for(; i<=N; i+=(i&-i)) tree[i]++; }
	int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
	int query(int l, int r) { return query(r)-query(l-1); }
};
BIT bit1, bit2;

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for(i=1; i<=M; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for(i=1; i<=N; i++) if(!vis[i]) dfs(i, i, 0), root[i]=1;

	//printf("ODD\n");
	//for(auto it : odd) printf("%d %d\n", it.first, it.second);

	//printf("EVEN\n");
	//for(auto it : even) printf("%d %d\n", it.first, it.second);

	for(auto &it : odd)
	{
		it.first=in[it.first]; it.second=in[it.second];
		if(it.first>it.second) swap(it.first, it.second);
	}

	for(auto &it : even)
	{
		it.first=in[it.first]; it.second=in[it.second];
		if(it.first>it.second) swap(it.first, it.second);
	}

	if(even.size()==1) ans++;

	//printf("DFSN\n");
	//for(i=1; i<=N; i++) printf("%d : %d %d\n", i, in[i], out[i]);

	vector<pii> todo;
	for(i=1; i<=N; i++)
	{
		if(root[i]) continue;
		todo.push_back({in[i], out[i]});
	}

	sort(odd.begin(), odd.end());
	sort(even.begin(), even.end());
	sort(todo.begin(), todo.end());

	i=0, j=0;
	for(auto it : todo)
	{
		for(; i<odd.size() && odd[i].first<it.first; i++) bit1.update(odd[i].second);
		for(; j<even.size() && even[j].first<it.first; j++) bit2.update(even[j].second);
		if(bit1.query(it.first, it.second)==0 && bit2.query(it.first, it.second)==even.size()) ans++;
	}

	printf("%d\n", ans);
}

Compilation message (stderr)

voltage.cpp: In function 'int main()':
voltage.cpp:101:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; i<odd.size() && odd[i].first<it.first; i++) bit1.update(odd[i].second);
         ~^~~~~~~~~~~
voltage.cpp:102:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j<even.size() && even[j].first<it.first; j++) bit2.update(even[j].second);
         ~^~~~~~~~~~~~
voltage.cpp:103:75: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(bit1.query(it.first, it.second)==0 && bit2.query(it.first, it.second)==even.size()) ans++;
                                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
voltage.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
voltage.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~

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