oj.uz

Submission #199737

# Submission time Handle Problem Language Result Execution time Memory
199737 2020-02-03T05:43:46 Z arnold518 전압 (JOI14_voltage) C++14
100 / 100
 245 ms 21868 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3576 KB Output is correct
2 Correct 8 ms 3576 KB Output is correct
3 Correct 7 ms 3576 KB Output is correct
4 Correct 7 ms 3576 KB Output is correct
5 Correct 8 ms 3576 KB Output is correct
6 Correct 8 ms 3576 KB Output is correct
7 Correct 8 ms 3704 KB Output is correct
8 Correct 9 ms 3580 KB Output is correct
9 Correct 8 ms 3576 KB Output is correct
10 Correct 8 ms 3676 KB Output is correct
11 Correct 8 ms 3572 KB Output is correct
12 Correct 8 ms 3576 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10608 KB Output is correct
2 Correct 140 ms 15592 KB Output is correct
3 Correct 76 ms 10608 KB Output is correct
4 Correct 108 ms 17524 KB Output is correct
5 Correct 15 ms 4600 KB Output is correct
6 Correct 132 ms 13348 KB Output is correct
7 Correct 140 ms 19552 KB Output is correct
8 Correct 141 ms 19624 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 10216 KB Output is correct
2 Correct 64 ms 19548 KB Output is correct
3 Correct 60 ms 19572 KB Output is correct
4 Correct 7 ms 3448 KB Output is correct
5 Correct 107 ms 13808 KB Output is correct
6 Correct 112 ms 10356 KB Output is correct
7 Correct 132 ms 14452 KB Output is correct
8 Correct 138 ms 16500 KB Output is correct
9 Correct 107 ms 15988 KB Output is correct
10 Correct 125 ms 14064 KB Output is correct
11 Correct 125 ms 10348 KB Output is correct
12 Correct 142 ms 12664 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 12520 KB Output is correct
2 Correct 102 ms 21868 KB Output is correct
3 Correct 10 ms 5240 KB Output is correct
4 Correct 144 ms 15600 KB Output is correct
5 Correct 150 ms 17136 KB Output is correct
6 Correct 139 ms 15412 KB Output is correct
7 Correct 227 ms 17772 KB Output is correct
8 Correct 214 ms 18920 KB Output is correct
9 Correct 241 ms 15980 KB Output is correct
10 Correct 223 ms 19612 KB Output is correct
11 Correct 217 ms 16364 KB Output is correct
12 Correct 222 ms 19696 KB Output is correct
13 Correct 160 ms 15596 KB Output is correct
14 Correct 201 ms 20952 KB Output is correct
15 Correct 245 ms 19936 KB Output is correct
16 Correct 206 ms 19376 KB Output is correct
17 Correct 162 ms 16996 KB Output is correct
18 Correct 164 ms 16868 KB Output is correct