QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#102759 | #5160. Kebab Pizza | w4p3r# | WA | 5ms | 23904kb | C++20 | 2.1kb | 2023-05-03 17:16:40 | 2023-05-03 17:16:42 |
Judging History
answer
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e - 6
#define FOR(i, a, b) for(int i = a;i <= b;i ++)
#define REP(i, a, b) for(int i = a;i >= b;i --)
#define pa pair<int, int>
#define fr first
#define sd second
#define pb push_back
#define db double
#define MEM(a) memset(a, 0, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
char ch = getchar();
ll s = 0, w = 1;
while (ch < '0' || ch > '9') {if (ch == '-')w = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
#define N 500010
int n, m;
int a[N], b[N];
vector<int>e[N];
int vst[N], st[N], top;
int d[N], deg[N], dep[N];
int flag = 0;
int id[N];
inline void ck(vector<int> G)
{
int tot = 0; int k = G.size();
for (int x : G)id[x] = ++ tot;
FOR(i, 1, m)
{
int x = a[i], y = b[i];
if ((!id[x]) && (!id[y])) {cout << "impossible\n"; exit(0);}
if (id[x] && id[y])
{
if (id[x] > id[y]) swap(x, y);
if ((id[y] != id[x] + 1) && (id[y] != k || id[x] != 1) && (x != y)) {cout << "impossible\n"; exit(0);}
}
}
cout << "possible\n";
}
void dfs(int x, int fa)
{
// cerr << "EE:" << x << '\n';
dep[x] = dep[fa] + 1;
st[++ top] = x; vst[x] = 1;
for (int y : e[x]) if (y != fa)
{
if (vst[y])
{
if(dep[y] > dep[x]) continue;
// cerr << "??:" << x << " " << y << endl;
// FOR(i, 1, top) cerr << st[i] << ' '; cerr << '\n';
vector<int> G;
while (st[top] != y)
{
G.pb(st[top--]);
}
G.pb(y);
ck(G); exit(0);
}
dfs(y, x);
}
top --;
}
int main()
{
m = read(), n = read();
FOR(i, 1, m)
{
a[i] = read(), b[i] = read();
if (a[i] != b[i])e[a[i]].pb(b[i]), e[b[i]].pb(a[i]);
}
FOR(i, 1, n)if (!vst[i]) {dfs(i, 0);}
FOR(i, 1, m)
{
if(a[i] != b[i]) deg[a[i]] ++, deg[b[i]] ++;
}
FOR(i, 1, n)d[i] = deg[i];
FOR(i, 1, n)if(deg[i] == 1)
{
for(int j : e[i]) d[j] --;
}
FOR(i, 1, n)if(d[i] > 2){cout << "impossible\n"; exit(0);}
cout << "possible\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 21800kb
input:
7 6 2 2 3 6 1 1 1 5 4 5 6 6 6 5
output:
possible
result:
ok single line: 'possible'
Test #2:
score: 0
Accepted
time: 5ms
memory: 19708kb
input:
5 5 1 3 1 5 2 3 2 5 3 4
output:
possible
result:
ok single line: 'possible'
Test #3:
score: 0
Accepted
time: 2ms
memory: 23808kb
input:
6 7 1 2 2 3 3 4 4 5 3 6 6 7
output:
impossible
result:
ok single line: 'impossible'
Test #4:
score: 0
Accepted
time: 2ms
memory: 23816kb
input:
8 4 1 1 1 2 2 1 2 2 3 3 3 4 4 3 4 4
output:
possible
result:
ok single line: 'possible'
Test #5:
score: 0
Accepted
time: 1ms
memory: 23904kb
input:
4 4 1 2 2 1 3 4 4 3
output:
possible
result:
ok single line: 'possible'
Test #6:
score: 0
Accepted
time: 1ms
memory: 23904kb
input:
5 4 1 1 1 4 2 2 2 4 3 4
output:
possible
result:
ok single line: 'possible'
Test #7:
score: -100
Wrong Answer
time: 2ms
memory: 21812kb
input:
6 4 1 1 1 4 2 2 2 4 3 3 3 4
output:
possible
result:
wrong answer 1st lines differ - expected: 'impossible', found: 'possible'