제출 #1288456

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288456		hainam2k9	다리 (APIO19_bridges)	C++20	73 / 100	3038 ms	7700 KiB

bridges

#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 1e5+5, SQRT = 500;
const string NAME = "";
struct Edge{
    int x,y,w,pos;
    bool operator<(const Edge& a){
        return w>a.w;
    }
}edge[MAXN],edge2[MAXN];
struct DSU{
    int par[MAXN],sz[MAXN];
    void init(int n){
        iota(par+1,par+n+1,1);
        fill(sz+1,sz+n+1,1);
    }
    int Find(int u){
        if(u==par[u]) return u;
        return par[u]=Find(par[u]);
    }
    void Union(int x, int y){
        x=Find(x), y=Find(y);
        if(x==y) return;
        if(sz[x]<sz[y]) swap(x,y);
        par[y]=x, sz[x]+=sz[y];
    }
}dsu;
int n,m,q,rs[MAXN],newval[MAXN];
bool vis[MAXN],vis2[MAXN];
vector<pair<int,int>> adj[MAXN];
vector<array<int,3>> upd,query;
int dfs(int u, int w){
    vis[u]=1;
    int sum=dsu.sz[u];
    for(pair<int,int>& e : adj[u])
        if(!vis[e.fi]&&w<=e.se) sum+=dfs(e.fi,w);
    return sum;
}
int main()
{
    tt;
    if(fopen((NAME + ".INP").c_str(), "r")) fo;
    cin >> n >> m;
    for(int i = 1; i<=m; ++i)
        cin >> edge[i].x >> edge[i].y >> edge[i].w, edge[i].pos=i, edge2[i]=edge[i];
    cin >> q;
    for(int i = 1; i<=q; ++i){
        int type,x,y;
        cin >> type >> x >> y;
        if(type==1) upd.push_back({x,y,i});
        else query.push_back({y,x,i});
        if(i==q||sz(upd)+sz(query)>SQRT){
            dsu.init(n);
            sort(edge+1,edge+m+1);
            sort(query.begin(),query.end(),greater<array<int,3>>());
            for(array<int,3>& b : upd)
                newval[b[0]]=b[1];
            int ptr=1;
            for(array<int,3>& a : query){
                while(ptr<=m&&edge[ptr].w>=a[0]){
                    if(newval[edge[ptr].pos]==0) dsu.Union(edge[ptr].x,edge[ptr].y);
                    ++ptr;
                }
                vector<int> v1,v2;
                for(int i = 0; i<=sz(upd); ++i)
                    if(i==sz(upd)||upd[i][2]>a[2]){
                        for(int j = i-1; j>=0; --j){
                            if(vis2[upd[j][0]]) continue;
                            vis2[upd[j][0]]=1;
                            int x=edge2[upd[j][0]].x, y=edge2[upd[j][0]].y, w=upd[j][1];
                            x=dsu.Find(x), y=dsu.Find(y);
                            adj[x].pb(y,w), adj[y].pb(x,w);
                            v1.pb(x), v1.pb(y), v2.pb(upd[j][0]);
                        }
                        for(int j = i; j<sz(upd); ++j){
                            if(vis2[upd[j][0]]) continue;
                            vis2[upd[j][0]]=1;
                            int x=edge2[upd[j][0]].x, y=edge2[upd[j][0]].y, w=edge2[upd[j][0]].w;
                            x=dsu.Find(x), y=dsu.Find(y);
                            adj[x].pb(y,w), adj[y].pb(x,w);
                            v1.pb(x), v1.pb(y), v2.pb(upd[j][0]);
                        }
                    }
                rs[a[2]]=dfs(dsu.Find(a[1]),a[0]);
                vis[dsu.Find(a[1])]=0;
                for(int& x : v1) adj[x].clear(), vis[x]=0;
                for(int& x : v2) vis2[x]=0;
            }
            for(int i = 1; i<=m; ++i)
                if(newval[edge[i].pos]!=0) edge[i].w=edge2[edge[i].pos].w=newval[edge[i].pos], newval[edge[i].pos]=0;
            upd.clear(), query.clear();
        }
    }
    for(int i = 1; i<=q; ++i)
        if(rs[i]!=0) cout << rs[i] << "\n";
}

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

bridges.cpp: In function 'int main()':
bridges.cpp:3:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:59:45: note: in expansion of macro 'fo'
   59 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~
bridges.cpp:3:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:59:45: note: in expansion of macro 'fo'
   59 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~

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