QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#746075#9525. Welcome to Join the Online Meeting!ssxWA 2ms9952kbC++202.8kb2024-11-14 13:17:072024-11-14 13:17:08

Judging History

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

  • [2024-11-14 13:17:08]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9952kb
  • [2024-11-14 13:17:07]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define pll pair<ll, ll>
#define ll long long
const int mod = 1e9 + 7;
const int N = 3e5 + 50;

vector<int> e[N];
int dfn[N], low[N], tot;
int stk[N], instk[N], top;
int scc[N], cnt;

void tarjan(int x) 
{
    dfn[x] = low[x] = ++tot;
    stk[++top] = x, instk[x] = 1;
    for (int y : e[x]) 
    {
        if (!dfn[y]) 
        {//若y尚未访问
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (instk[y])//若y已访问且在栈中
            low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x]) 
    {//若x是SCC的根
        int y; ++cnt;
        do {
            y = stk[top--];
            instk[y] = 0;
            scc[y] = cnt; //y属于哪个SCC
        } while (y != x);
    }
}

ll st[N], vis[N];
ll in[N], out[N];

void bfs(ll s)
{
    cout << s << '\n';
    vector<ll> v;
    queue<ll> q;
    q.push(s);
    vis[s] = 1;
    while (!q.empty())
    {
        auto tx = q.front();
        q.pop();
        v.clear();
        for (auto it : e[tx])
        {
            if (vis[it] == 1) continue;
            vis[it] = 1;
            v.push_back(it);
            q.push(it);
        }
        if (v.size() == 0) continue;
        cout << tx << ' ' << v.size() << ' ';
        for (auto it : v) cout << it << ' ';
        cout << '\n';
    }

}

void solve()
{
    ll n, m, k, a0, res = 0, start = 0;
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++)
    {
        cin >> a0;
        st[a0] = 1;
    }
    ll u, v;
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v;
        if (st[u] == 1 && st[v] == 1) continue;
        if (st[u] == 1 && st[v] == 0) e[v].push_back(u);
        else
        {
            if (st[u] == 0 && st[v] == 1) e[u].push_back(v);
            else 
            {
                e[u].push_back(v);
                e[v].push_back(u);
            }
        }
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);
    
    for (int x = 1; x <= n; x++) 
    {
        for (int y : e[x]) 
        {
            ll a = scc[x], b = scc[y];
            if (a != b) in[scc[y]] ++;
        }
    } //缩点后建拓扑图
    for (int i = 1; i <= cnt; i++)
    {
        if (in[i] == 0)
        {
            res ++;
            start = i;
        }
    }
    if (res > 1) cout << "NO";
    else
    {
        cout << "YES" << '\n';
        for (int i = 1; i <= n; i++)
        {
            if (scc[i] == start)
            {
                start = i;
                break;
            }
        }
        bfs(start);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll T = 1;
    //cin >> T;
    while (T --)
    {
        solve();
    }
    
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 9952kb

input:

4 5 2
3 4
1 2
1 3
2 3
3 4
2 4

output:

YES
1
1 2 2 3 
2 1 4 

result:

wrong answer Token parameter [name=pans] equals to "YES", doesn't correspond to pattern "Yes|No"