제출 #707606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707606		He_Huanglu	다리 (APIO19_bridges)	C++17	0 / 100	3054 ms	6128 KiB

bridges

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;

const int N = 5e4 + 5, L = 1e5 + 5;
int n, m, q, from[L], to[L], d[L], par[N], ok[L], ans[L];
pair<int, ii> lst[L];
stack <ii> st;


int root(int u)
{
    return par[u] < 0 ? u : root(par[u]);
}
void join(int u, int v, int tp)
{
    u = root(u), v = root(v);
    if(u == v) return ;
    if(par[u] > par[v]) swap(u, v);
    if(tp)
    {
        st.push({v, par[v]});
        st.push({u, par[u]});
    }
    par[u] += par[v];
    par[v] = u;
}
void undo()
{
    while (!st.empty())
    {
        par[st.top().fi] = st.top().se;
        st.pop();
    }
}


main ()
{
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("task.inp", "r"))
    {
        freopen("task.inp", "r", stdin);
        freopen("wa.out", "w", stdout);
    }
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> from[i] >> to[i] >> d[i];
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        cin >> lst[i].fi >> lst[i].se.fi >> lst[i].se.se;
    }
    const int S = sqrt(q);
    int lim = ceil(1.0 * q / S);
    for(int t = 0; t < lim; t++)
    {
        vector <pair<int, ii> > change, query;
        vector <int> remain;
        for(int i = min(q, (t + 1) * S); i >= t * S + 1; i--)
        {
            if(lst[i].fi == 1)
            {
                ok[lst[i].se.fi] = 1;
//                if(t == 2)
//                {
//                    cout << lst[i].se.fi << "&&\n";
//                    for(int i = 1; i <= m; i++) cout << ok[i] << " ";
//                    cout << "\n";
//                }
                change.push_back({i, lst[i].se});
            }
            else query.push_back({i, lst[i].se});
        }
        for(int i = 1; i <= m; i++)
        {
            if(!ok[i])
            {
                remain.push_back(i);
//                if(t == 2) cout << i << "$$\n";
            }
            else change.push_back({0, {i, d[i]}});
        }
        sort(remain.begin(), remain.end(), [] (int x, int y) {
             return d[x] > d[y];
        });
        sort(query.begin(), query.end(), [] (pair<int, ii> x, pair<int, ii> y) {
             return x.se.se > y.se.se;
        });
//        sort(change.begin(), change.end(), [] )
        for(int i = 1; i <= n; i++) par[i] = -1;
        while (!st.empty()) st.pop();
        int it = 0;
//        cout << change.size() << "###\n";
        for(int i = 0; i < remain.size(); i++)
        {
            int j = remain[i];
//            if(t == 1) cout << j << " : " << d[j] << "%%\n";
        }
//        if(t == 1) cout << d[3] << "^\n";
//        cout << "\n";
        for(auto[id, e] : query)
        {
            int x = e.fi, w = e.se;
//            if(t == 1) cout << id << " " << x << " " << w << "***\n";
            while (it < remain.size() && d[remain[it]] >= w)
            {
                int i = remain[it];
//                if(t == 1) cout << i << " : " << from[i] << " " << to[i] << " " << d[i] << "^^\n";
                join(from[i], to[i], 0);
                it++;
            }
            for(auto[jd, _e] : change)
            {
                int i = _e.fi, r = _e.se;
//                if(t == 1) cout << i << " " << ok[i] << " " << r << "$$$\n";
                if(jd < id && r >= w && ok[i] != 2)
                {
                    join(from[i], to[i], 1);
//                    if(t == 1) cout << i << " : " << from[i] << " " << to[i] << " " << r << "^^^^\n";
                }
                if(jd < id) ok[i] = 2;
            }
            ans[id] = -par[root(x)];
//            if(t == 1) cout << id << " " << ans[id] << "\n";
            undo();
        }
        for(int i = t * S + 1; i <= min(q, (t + 1) * S); i++)
        {
            if(lst[i].fi == 1)
            {
                ok[lst[i].se.fi] = 0;
                d[lst[i].se.fi] = lst[i].se.se;
//                cout << i << " " << lst[i].se.fi << " " << d[lst[i].se.fi] << "##\n";
            }
        }
    }
    for(int i = 1; i <= q; i++) if(lst[i].fi == 2) cout << ans[i] << "\n";

}

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main ()
      | ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:96:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int i = 0; i < remain.size(); i++)
      |                        ~~^~~~~~~~~~~~~~~
bridges.cpp:98:17: warning: unused variable 'j' [-Wunused-variable]
   98 |             int j = remain[i];
      |                 ^
bridges.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             while (it < remain.size() && d[remain[it]] >= w)
      |                    ~~~^~~~~~~~~~~~~~~
bridges.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen("wa.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27