QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#690008#3001. Piece of CakebluejellyfishRE 0ms0kbC++231.6kb2024-10-30 19:43:462024-10-30 19:43:46

Judging History

你现在查看的是最新测评结果

  • [2024-10-30 19:43:46]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-30 19:43:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ing long long
#define pii pair<int,int>
#define x first
#define y second
void miss() {
	int n,m;
	while(cin >> n >> m) {
		vector<int>dfn(n * 2 + 10),low(n * 2 + 10),tp(n * 2 + 10),cl(n * 2 + 10);
		vector<vector<int>>mp(n * 2 + 10);
		int cnt = 0,zlm = 0;	
		for(int i = 1; i <= m; i++) {
			int a,b;
			cin >> a >> b;
			if(a < 0) a = (-a) << 1;
			else a = a << 1 | 1;
			if(b < 0) b = (-b) << 1;
			else b = b << 1 | 1;
			mp[a].push_back(b ^ 1);
			mp[b].push_back(a ^ 1);
		}
		stack<int>q;
		vector<bool>is(n * 2 + 10);
		auto tarjan =[&] (auto self,int x) -> void {
			low[x] = dfn[x] = ++cnt;
			is[x] = 1;
			q.push(x);
			for(auto v : mp[x]) {
				if(!dfn[x]) {
					self(self,v);
					low[x] = min(low[x],low[v]);
				}else if(is[v])low[x] = min(low[x],dfn[v]);
			}
			if(low[x] == dfn[x]) {
				zlm++;
				do{
					x = q.top();q.pop();
					is[x] = 0;
					tp[x] = zlm;
				} while(low[x] != dfn[x]);
			}
 		};
		for(int i = 1; i <= n; i++) {
			if(!dfn[i << 1]) tarjan(tarjan,i << 1);
			if(!dfn[i << 1 | 1]) tarjan(tarjan,i << 1 | 1);
		}
		auto dfs =[&] (auto self,int x) -> void {
			cl[x] = 1;
			for(auto v : mp[x]) {
				if(!cl[v]) self(self,v);
			}
		};
		dfs(dfs,3);
		bool fg = 0;
		for(int i = 1; i <= n; i++) {
			if(tp[i << 1] == tp[i << 1 | 1]) fg = 1;
			if(cl[i << 1] && cl[i << 1 | 1]) fg = 1;
		}
		if(fg) cout << "no\n";
		else cout << "yes\n";
	}
}
signed main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T = 1;
	//cin >> T;
	while(T--) miss();
}

詳細信息

Test #1:

score: 0
Runtime Error

input:

3 3
-5.236334 -8.519438
-9.987847 -0.492878
-9.994555 0.329962

output:


result: