Submission #1264233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264233		MongHwa	철도 요금 (JOI16_ho_t3)	C++20	26 / 100	49 ms	13896 KiB

2016_ho_t3

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dist[100005];
int u[200005], v[200005], val[100005];
vector<int> stage[100005], vec[100005];
queue<int> qu;

void bfs()
{
    dist[1] = 1;
    qu.push(1);
    while(!qu.empty())
    {
        int cur = qu.front(); qu.pop();

        for(int nxt : stage[cur])
            if(dist[nxt] == 0 || dist[nxt] == dist[cur]+1)
            {
                if(dist[nxt] == 0)
                    qu.push(nxt);
                dist[nxt] = dist[cur]+1;
                vec[cur].push_back(nxt);
                val[nxt]++;
            }
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 0; i < m; i++)
    {
        cin >> u[i] >> v[i];
        stage[u[i]].push_back(v[i]);
        stage[v[i]].push_back(u[i]);
    }

    bfs();
    int ans = 0;
    while(q--)
    {
        int r;
        cin >> r; r--;

        if(dist[u[r]] != dist[v[r]])
        {
            if(dist[u[r]] > dist[v[r]])
                swap(u[r], v[r]);
            val[v[r]]--;
            if(val[v[r]] == 0)
            {
                qu.push(v[r]);
                while(!qu.empty())
                {
                    ans++;
                    int cur = qu.front(); qu.pop();
                    for(int nxt : vec[cur])
                    {
                        val[nxt]--;
                        if(val[nxt] == 0)
                            qu.push(nxt);
                    }
                }
            }
        }

        cout << ans << '\n';
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 14 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 39