QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#690008 | #3001. Piece of Cake | bluejellyfish | RE | 0ms | 0kb | C++23 | 1.6kb | 2024-10-30 19:43:46 | 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