QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#24221 | #1825. The King's Guards | p_b_p_b | WA | 547ms | 16504kb | C++17 | 4.0kb | 2022-03-27 20:10:09 | 2022-04-30 05:16:19 |
Judging History
answer
#include<bits/stdc++.h>
namespace my_std{
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,x,y) for (int i=(x);i>=(y);i--)
#define go(x) for (int i=head[x];i;i=edge[i].nxt)
#define templ template<typename T>
typedef long long ll;
typedef double db;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
templ inline void read(T& t)
{
t=0;char f=0,ch=getchar();double d=0.1;
while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
t=(f?-t:t);
}
template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
char __sr[1<<21],__z[20];int __C=-1,__zz=0;
inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
inline void print(int x)
{
if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
while(__z[++__zz]=x%10+48,x/=10);
while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
}
void file()
{
#ifdef NTFOrz
freopen("a.in","r",stdin);
#endif
}
inline void chktime()
{
#ifdef NTFOrz
cerr<<clock()/1000.0<<'\n';
#endif
}
#ifdef mod
ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
ll inv(ll x){return ksm(x,mod-2);}
#else
ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
#endif
// inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;
namespace Flow
{
#define sz 505050
int n,S,T;
struct hh{int t,w,c,nxt;}edge[sz<<1];
int head[sz],ecnt=1;
void make_edge(int f,int t,int w,int c)
{
c=-c;
edge[++ecnt]=(hh){t,w,c,head[f]};
head[f]=ecnt;
edge[++ecnt]=(hh){f,0,-c,head[t]};
head[t]=ecnt;
}
int dis[sz],flow[sz];
int pre[sz];
bool in[sz];
bool SPFA()
{
rep(i,1,n) dis[i]=1e9,flow[i]=0,pre[i]=0;
queue<int>q;
q.push(S);dis[S]=0;flow[S]=1e9;in[S]=1;
#define v edge[i].t
while (!q.empty())
{
int x=q.front();q.pop();in[x]=0;
go(x)
if (edge[i].w&&chkmin(dis[v],dis[x]+edge[i].c))
flow[v]=min(flow[x],edge[i].w),pre[v]=i,(!in[v]&&(q.push(v),0)),in[v]=1;
}
#undef v
return dis[T]!=1e9;
}
int mxflow,mncost;
void update(){int f=flow[T];mxflow+=f;mncost+=dis[T]*f;for (int x=T,i;i=pre[x],x!=S;x=edge[i^1].t) edge[i].w-=f,edge[i^1].w+=f;}
int work(){while (SPFA()) update();return -mncost;}
#undef sz
}
namespace Build
{
#define sz 333
int n,m,K;
int S,T;
struct hh{int u,v,w;bool operator < (const hh &a) const {return w<a.w;}}e[sz*sz];
int fa[sz];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
vector<int>V[sz];
void dfs(int x,int f)
{
Flow::make_edge(x*2-1,x*2,1,0);
for (auto ee:V[x])
{
int v=e[ee].u^e[ee].v^x; if (v==f) continue;
Flow::make_edge(v*2,x*2-1,1,0);
Flow::make_edge(v*2,T,1,e[ee].w);
dfs(v,x);
}
}
void work()
{
read(n,m,K);
S=n*2+K+1,T=S+1;
int x,y,z;
rep(i,1,m) read(x,y,z),e[i]=(hh){x,y,z};
sort(e+1,e+m+1);
rep(i,1,n) fa[i]=i;
ll ans=0;
rep(i,1,m)
{
x=e[i].u,y=e[i].v;
if (getfa(x)!=getfa(y)) V[x].push_back(i),V[y].push_back(i),fa[fa[x]]=fa[y],ans+=e[i].w;
}
const int MX=333333; int c=0;
rep(i,1,n) if (i==fa[i]) dfs(i,0),Flow::make_edge(i*2,T,1,MX),++c;
rep(i,1,K)
{
Flow::make_edge(S,n*2+i,1,0);
int k; read(k);
while (k--) read(x),Flow::make_edge(n*2+i,x*2-1,1,0);
}
Flow::n=Flow::T=T; Flow::S=S;
ans-=Flow::work();
ans+=c*MX;
if (Flow::mxflow==K) cout<<ans<<'\n';
else puts("-1");
}
}
int main()
{
file();
Build::work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 13904kb
input:
5 6 2 1 2 1 1 3 4 2 4 2 2 5 5 3 4 7 4 5 3 2 1 2 2 2 4
output:
8
result:
ok answer is '8'
Test #2:
score: 0
Accepted
time: 2ms
memory: 15916kb
input:
10 19 6 1 5 761 6 8 606 3 9 648 2 4 115 5 8 814 1 2 712 4 10 13 5 10 797 3 4 956 1 7 73 5 7 192 2 7 110 5 9 302 3 6 120 6 9 494 1 3 668 3 7 966 6 10 974 3 8 41 2 10 5 3 6 4 3 2 1 7 2 10 8 3 10 7 8 2 2 1
output:
429
result:
ok answer is '429'
Test #3:
score: 0
Accepted
time: 0ms
memory: 16016kb
input:
10 43 3 1 3 656 2 6 856 4 10 99 5 6 900 2 7 766 4 7 582 2 8 135 5 7 831 3 5 12 3 10 789 1 8 66 4 9 390 1 7 238 6 7 960 1 4 624 3 9 602 7 10 366 5 8 526 2 9 561 6 10 722 2 5 904 3 4 35 1 9 768 5 9 457 6 8 61 4 6 192 4 5 96 5 10 747 8 9 611 7 8 953 3 8 449 2 4 228 1 6 197 9 10 160 3 6 869 1 2 785 4 8 ...
output:
526
result:
ok answer is '526'
Test #4:
score: 0
Accepted
time: 3ms
memory: 14000kb
input:
277 9038 1 226 260 740 44 226 376 151 263 611 67 269 241 120 181 677 259 271 782 37 52 310 48 152 452 168 266 823 85 234 100 46 201 738 129 153 301 69 147 434 13 72 764 13 234 316 171 222 398 214 255 21 112 158 430 20 118 407 45 152 971 205 214 272 221 275 362 198 268 472 117 176 207 31 75 652 139 1...
output:
5375
result:
ok answer is '5375'
Test #5:
score: 0
Accepted
time: 13ms
memory: 15956kb
input:
297 27966 132 15 197 980 226 259 950 161 168 142 118 176 834 157 221 806 24 210 432 212 242 838 110 166 177 78 170 801 52 166 3 89 213 448 45 170 626 250 251 268 93 222 679 7 128 839 5 7 320 132 191 1 192 295 717 36 231 542 162 175 508 173 178 458 211 272 926 46 168 145 19 150 805 165 262 198 50 179...
output:
775
result:
ok answer is '775'
Test #6:
score: 0
Accepted
time: 6ms
memory: 15936kb
input:
7 7 4 1 3 7 1 4 6 2 3 5 2 4 6 4 5 10 4 6 10 4 7 10 5 4 3 2 7 5 6 5 2 6 7 4 1 2 2 3 6 7 2 5 3 1 6
output:
17
result:
ok answer is '17'
Test #7:
score: 0
Accepted
time: 209ms
memory: 16504kb
input:
300 44850 299 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 1 8 1 1 9 1 1 10 1 1 11 1 1 12 1 1 13 1 1 14 1 1 15 1 1 16 1 1 17 1 1 18 1 1 19 1 1 20 1 1 21 1 1 22 1 1 23 1 1 24 1 1 25 1 1 26 1 1 27 1 1 28 1 1 29 1 1 30 1 1 31 1 1 32 1 1 33 1 1 34 1 1 35 1 1 36 1 1 37 1 1 38 1 1 39 1 1 40 1 1 41 1 1 42 1 1 43 1 ...
output:
1000
result:
ok answer is '1000'
Test #8:
score: 0
Accepted
time: 547ms
memory: 16484kb
input:
300 44850 299 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 1 8 1 1 9 1 1 10 1 1 11 1 1 12 1 1 13 1 1 14 1 1 15 1 1 16 1 1 17 1 1 18 1 1 19 1 1 20 1 1 21 1 1 22 1 1 23 1 1 24 1 1 25 1 1 26 1 1 27 1 1 28 1 1 29 1 1 30 1 1 31 1 1 32 1 1 33 1 1 34 1 1 35 1 1 36 1 1 37 1 1 38 1 1 39 1 1 40 1 1 41 1 1 42 1 1 43 1 ...
output:
1000
result:
ok answer is '1000'
Test #9:
score: 0
Accepted
time: 46ms
memory: 16444kb
input:
300 44850 150 1 2 4 1 3 4 1 4 4 1 5 3 1 6 10 1 7 4 1 8 8 1 9 5 1 10 4 1 11 9 1 12 9 1 13 1 1 14 3 1 15 5 1 16 7 1 17 5 1 18 2 1 19 6 1 20 4 1 21 10 1 22 5 1 23 7 1 24 2 1 25 2 1 26 4 1 27 4 1 28 5 1 29 8 1 30 10 1 31 9 1 32 1 1 33 7 1 34 5 1 35 4 1 36 6 1 37 8 1 38 1 1 39 2 1 40 1 1 41 1 1 42 1 1 43...
output:
249
result:
ok answer is '249'
Test #10:
score: 0
Accepted
time: 59ms
memory: 16388kb
input:
300 44850 150 1 2 70 1 3 26 1 4 76 1 5 74 1 6 98 1 7 72 1 8 66 1 9 25 1 10 36 1 11 57 1 12 8 1 13 88 1 14 98 1 15 33 1 16 85 1 17 56 1 18 16 1 19 62 1 20 41 1 21 81 1 22 18 1 23 15 1 24 69 1 25 11 1 26 29 1 27 62 1 28 64 1 29 41 1 30 92 1 31 29 1 32 99 1 33 40 1 34 30 1 35 23 1 36 49 1 37 6 1 38 84 ...
output:
1299
result:
ok answer is '1299'
Test #11:
score: 0
Accepted
time: 65ms
memory: 16032kb
input:
300 44850 150 1 2 3 1 3 2 1 4 20 1 5 77 1 6 77 1 7 23 1 8 39 1 9 57 1 10 83 1 11 60 1 12 6 1 13 78 1 14 64 1 15 62 1 16 41 1 17 88 1 18 77 1 19 58 1 20 39 1 21 18 1 22 43 1 23 26 1 24 40 1 25 61 1 26 23 1 27 6 1 28 47 1 29 100 1 30 59 1 31 92 1 32 60 1 33 13 1 34 57 1 35 55 1 36 99 1 37 77 1 38 63 1...
output:
1310
result:
ok answer is '1310'
Test #12:
score: -100
Wrong Answer
time: 16ms
memory: 16408kb
input:
300 44551 299 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 1 8 1 1 9 1 1 10 1 1 11 1 1 12 1 1 13 1 1 14 1 1 15 1 1 16 1 1 17 1 1 18 1 1 19 1 1 20 1 1 21 1 1 22 1 1 23 1 1 24 1 1 25 1 1 26 1 1 27 1 1 28 1 1 29 1 1 30 1 1 31 1 1 32 1 1 33 1 1 34 1 1 35 1 1 36 1 1 37 1 1 38 1 1 39 1 1 40 1 1 41 1 1 42 1 1 43 1 ...
output:
333333
result:
wrong answer expected '-1', found '333333'