Submission #561809

#TimeUsernameProblemLanguageResultExecution timeMemory
561809fcmalkcinReconstruction Project (JOI22_reconstruction)C++17
100 / 100
1951 ms34328 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define ff first #define ss second #define pb push_back #define endl "\n" mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); const ll maxn=503; const ll maxn1=1e5+10; const ll mod=1e9+7 ; const ll base=1e9; /// i believe myself /// goal 2/7 ll par[maxn]; ll find_par(ll u) { if (par[u]<0) return u; return par[u]=find_par(par[u]); } bool dsu(ll x,ll y) { x=find_par(x); y=find_par(y); if (x==y) return false; if (par[x]>par[y]) swap(x,y); par[x]+=par[y]; par[y]=x; return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen("t.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } ll n, m; cin>> n>> m; vector<pair<ll,pll>> vt; vector<ll> vt1; for (int i=1; i<=m; i++) { ll x, y, w; cin>> x>> y>> w; vt.pb(make_pair(w,make_pair(x,y))); } sort(vt.begin(),vt.end()); vector<pair<ll,pll>> vt2; for (int i=1;i<=m;i++) { ll j=i+1; memset(par,-1,sizeof(par)); while (j<=m) { dsu(vt[j-1].ss.ff,vt[j-1].ss.ss); if (find_par(vt[i-1].ss.ff)==find_par(vt[i-1].ss.ss)) { break; } j++; } ll k=i-1; memset(par,-1,sizeof(par)); while (k) { dsu(vt[k-1].ss.ff,vt[k-1].ss.ss); if (find_par(vt[i-1].ss.ff)==find_par(vt[i-1].ss.ss)) { break; } k--; } vt2.pb(make_pair((k==0?-1:(vt[k-1].ff+vt[i-1].ff+1)/2),make_pair(-1,vt[i-1].ff))); vt2.pb(make_pair(vt[i-1].ff,make_pair(2,-2*vt[i-1].ff))); vt2.pb(make_pair((j==m+1?base+1:(vt[j-1].ff+vt[i-1].ff+1)/2),make_pair(-1,vt[i-1].ff))); } ll sl=0; ll cnt=0; ll q; cin>> q; sort(vt2.begin(),vt2.end()); ll id=0; for (int i=1;i<=q;i++) { ll x; cin>> x; while (id<vt2.size()&&vt2[id].ff<=x) { auto p=vt2[id].ss; sl+=p.ff; cnt+=p.ss; id++; } cout <<sl*x+cnt<<endl; } }

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:102:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         while (id<vt2.size()&&vt2[id].ff<=x)
      |                ~~^~~~~~~~~~~
reconstruction.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...