Submission #1264234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264234		MongHwa	철도 요금 (JOI16_ho_t3)	C++20	100 / 100	112 ms	27288 KiB

2016_ho_t3

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

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

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);
                rev[nxt].insert(cur);
            }
    }
}
 
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]);
            if(rev[v[r]].find(u[r]) != rev[v[r]].end())
            {
                rev[v[r]].erase(u[r]);
                if(rev[v[r]].empty())
                {
                    qu.push(v[r]);
                    while(!qu.empty())
                    {
                        ans++;
                        int cur = qu.front(); qu.pop();
                        for(int nxt : vec[cur])
                            if(rev[nxt].find(cur) != rev[nxt].end())
                            {
                                rev[nxt].erase(cur);
                                if(rev[nxt].empty())
                                    qu.push(nxt);
                            }
                    }
                }
            }
        }

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

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