QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#414103 | #7986. 游戏 | aurorawhitesea | ML | 0ms | 0kb | C++14 | 1.4kb | 2024-05-18 15:21:33 | 2024-05-18 15:21:33 |
answer
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int head[100005], cnt, n, l, r, dep[100005], dep1[100005], num[100005];
bool flag[100005]={0};
vector<int>v[100005];
struct tree
{
int to;
int next;
}c[100005];
void add(int a, int b)
{
v[a].push_back(b);
}
int dfs1(int x)
{
if (v[x].size() == 0)
{
dep1[x]=1;
return 1;
}
for (int i = 0; i<v[x].size(); i++)
{
int t=dfs1(v[x][i]);
if(i==0)dep1[x]=t+1;
else dep1[x]=min(dep1[x],t+1);
}
return dep1[x];
}
void dfs(int x)
{
if(dep1[x]==1)
{
flag[x]=1;
return;
}
int cnt=0;
for(int i=0;i<v[x].size();i++)
{
dfs(v[x][i]);
if(flag[v[x][i]])
{
cnt++;
}
}
if(cnt>=2)flag[x]=1;
}
int main()
{
cin >> n;
if( n == 1)
{
cout << "Wasted." << endl;
return 0;
}
for (int i = 1; i <= n; i++)
{
dep1[i] = 0x3f3f3f3f;
}
for (int i = 1; i <= n - 1; i++)
{
cin >> l >> r;
add(l, r);
add(r,l);
}
dfs1(1);
dfs(1);
bool ff=flag[1];
if (ff)
{
cout << "You win, temporarily." << endl;
}
else
{
cout << "Wasted." << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
6 1 2 2 3 2 4 1 5 5 6