1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const ll db[11][11]={
 5 {0},
 6 {0,0},
 7 {0,-1,1},
 8 {0,-1,-2,8},
 9 {0,2,3,4,4},
10 {0,-1,-2,7,5,6},
11 {0,-1,-1,8,6,7,8}
12 };
13 ll n,m;
14 int main()
15 {
16     scanf("%lld%lld",&n,&m);
17 //    printf("%lld %lld\n",n,m);
18     if(!n || !m) { printf("-1\n"); return 0; }
19     ll ans=0;
20     if(n>6) { int nn=(n-4)/3; ans+=nn*2; n=(n-4)%3+4; }
21     if(m>6) { int mm=(m-4)/3; ans+=mm*2; m=(m-4)%3+4; }
22 //    while(n>6) n-=3,ans+=2;
23 //    while(m>6) m-=3,ans+=2;
24     if(n<m) n^=m^=n^=m;
25 //    printf("%lld %lld\n",n,m);
26     if(db[n][m]==-1) printf("-1\n");
27     else printf("%lld\n",ans+db[n][m]);
28     return 0;
29 }

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=2e5+11,M=1e6+11;
 4 int n,m,ansx,ansy;
 5 int fr[M],to[M],nxt[M],edge,head[N];
 6 int dfn[N],low[N],tot,sta[N],top;
 7 int cnt,tag[N],chu[N],ru[N];
 8 bool vis[N];
 9  
10 inline int re_ad() {
11     char ch=getchar(); int x=0,f=1;
12     while(ch<'0' || ch>'9') { if(ch=='-') f=-1 ;ch=getchar(); }
13     while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
14     return x*f;
15 }
16  
17 inline void addedge(int x,int y) {
18     ++edge,fr[edge]=x,to[edge]=y,nxt[edge]=head[x],head[x]=edge;
19 }
20  
21 void tarjan(int d) {
22     dfn[d]=low[d]=++tot,sta[++top]=d,vis[d]=true;
23     for(int i=head[d];i;i=nxt[i])
24         if(!dfn[to[i]]) tarjan(to[i]),low[d]=min(low[d],low[to[i]]);
25         else if(vis[to[i]]) low[d]=min(low[d],dfn[to[i]]);
26     if(dfn[d]!=low[d]) return ;
27     tag[d]=++cnt;
28     while(sta[top]!=d) tag[sta[top]]=cnt,vis[sta[top]]=false,--top;
29     vis[d]=false,--top;
30 }
31  
32 int main()
33 {
34     n=re_ad(),m=re_ad();
35     for(int i=1,x,y;i<=m;++i) x=re_ad(),y=re_ad(),addedge(x,y);
36     for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
37     for(int i=1;i<=m;++i) if(tag[fr[i]]!=tag[to[i]]) ++chu[tag[fr[i]]],++ru[tag[to[i]]];
38     if(cnt==1) { printf("0\n"); return 0; }
39     for(int i=1;i<=cnt;++i) ansx+=(ru[i]==0),ansy+=(chu[i]==0);
40     printf("%d\n",max(ansx,ansy));
41     return 0;
42 }

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=2e6+11,inf=1<<30;
 4 int n,m,k,t[N],dis[N];
 5 int to[N],nxt[N],w[N],edge,head[N],hhead[N];
 6 bool vis[N];
 7   
 8 inline int re_ad() {
 9     char ch=getchar(); int x=0,f=1;
10     while(ch<'0' || ch>'9') { if(ch=='-') f=-1 ;ch=getchar(); }
11     while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
12     return x*f;
13 }
14 inline void addedge(int x,int y,int z,int k) {
15     ++edge,to[edge]=y,nxt[edge]=head[x],w[edge]=z,head[x]=edge;
16     if(!k) hhead[x]=edge;
17 }
18   
19 inline void SPFA(int d) {
20     deque<int> q;
21     memset(dis,0x3f,sizeof(dis));
22     memset(vis,false,sizeof(vis));
23     dis[d]=0,vis[d]=true;
24     q.push_back(d);
25     while(!q.empty()) {
26         int u=q.front(); q.pop_front();
27         for(int i=head[u],v;i;i=nxt[i]) {
28             v=to[i];
29             if(dis[u]+w[i]<dis[v]) {
30                 dis[v]=dis[u]+w[i];
31                 if(!vis[v]) {
32                     vis[v]=true;
33                     (dis[v]<=dis[q.front()])?q.push_front(v):q.push_back(v);
34                 }
35             }
36         }
37     }
38 }
39   
40 int main()
41 {
42     n=re_ad(),m=re_ad(),k=re_ad();
43     for(int i=1,x,y,z;i<=m;++i) x=re_ad(),y=re_ad(),z=re_ad(),addedge(x,y,z,0);
44     for(int i=1;i<=k;++i) t[i]=re_ad();
45     int ans=inf;
46     for(int bt=0;bt<=14;++bt) {
47         edge=m; for(int i=1;i<=n+2;++i) head[i]=hhead[i];
48         for(int i=1;i<=k;++i) i&(1<<bt)?addedge(n+1,t[i],0,1):addedge(t[i],n+2,0,1);
49         SPFA(n+1); ans=min(ans,dis[n+2]);
50 //      for(int i=1;i<=n+2;++i) printf("%d ",dis[i]); puts("");
51         edge=m; for(int i=1;i<=n+2;++i) head[i]=hhead[i];
52         for(int i=1;i<=k;++i) i&(1<<bt)?addedge(t[i],n+2,0,1):addedge(n+1,t[i],0,1);
53         SPFA(n+1); ans=min(ans,dis[n+2]);
54 //      for(int i=1;i<=n+2;++i) printf("%d ",dis[i]); puts("");
55     }
56     printf("%d\n",ans);
57     return 0;
58 }

#include<bits/stdc++.h> using namespace std; const int N=2e6+11,inf=1<<30; int n,m,k,t[N],dis[N]; int to[N],nxt[N],w[N],edge,head[N],hhead[N]; bool vis[N];    inline int re_ad() {     char ch=getchar(); int x=0,f=1;     while(ch<'0' || ch>'9') { if(ch=='-') f=-1 ;ch=getchar(); }     while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();     return x*f; } inline void addedge(int x,int y,int z,int k) {     ++edge,to[edge]=y,nxt[edge]=head[x],w[edge]=z,head[x]=edge;     if(!k) hhead[x]=edge; }    inline void SPFA(int d) {     deque<int> q;     memset(dis,0x3f,sizeof(dis));     memset(vis,false,sizeof(vis));     dis[d]=0,vis[d]=true;     q.push_back(d);     while(!q.empty()) {         int u=q.front(); q.pop_front();         for(int i=head[u],v;i;i=nxt[i]) {             v=to[i];             if(dis[u]+w[i]<dis[v]) {                 dis[v]=dis[u]+w[i];                 if(!vis[v]) {                     vis[v]=true;                     (dis[v]<=dis[q.front()])?q.push_front(v):q.push_back(v);                 }             }         }     } }    int main() {     n=re_ad(),m=re_ad(),k=re_ad();     for(int i=1,x,y,z;i<=m;++i) x=re_ad(),y=re_ad(),z=re_ad(),addedge(x,y,z,0);     for(int i=1;i<=k;++i) t[i]=re_ad();     int ans=inf;     for(int bt=0;bt<=14;++bt) {         edge=m; for(int i=1;i<=n+2;++i) head[i]=hhead[i];         for(int i=1;i<=k;++i) i&(1<<bt)?addedge(n+1,t[i],0,1):addedge(t[i],n+2,0,1);         SPFA(n+1); ans=min(ans,dis[n+2]); //      for(int i=1;i<=n+2;++i) printf("%d ",dis[i]); puts("");         edge=m; for(int i=1;i<=n+2;++i) head[i]=hhead[i];         for(int i=1;i<=k;++i) i&(1<<bt)?addedge(t[i],n+2,0,1):addedge(n+1,t[i],0,1);         SPFA(n+1); ans=min(ans,dis[n+2]); //      for(int i=1;i<=n+2;++i) printf("%d ",dis[i]); puts("");     }     printf("%d\n",ans);     return 0; }