Submission #2756277
Source Code Expand
#include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <queue> #include <vector> #include <functional> #include <map> #include <set> #include <cmath> #include <string> #define SIZE 4910 #define INF 10000005 using namespace std; typedef long long int ll; typedef pair <int,int> P; int n; int X,Y,E; ll K; struct edge{int to,cap,rev;}; vector<edge> G[SIZE]; bool used[SIZE]; //グラフ追加: from -> to (cap) void add_edge(int from, int to, int cap){ G[from].push_back((edge){to,cap,(int)G[to].size()}); G[to].push_back((edge){from,0,(int)G[from].size()-1}); } //パスを一本見つける int dfs(int v, int t, int f){ if(v==t)return f; used[v] = true; for(int i=0;i<G[v].size();i++){ edge &e = G[v][i]; if(!used[e.to] && e.cap>0){ int d = dfs(e.to,t,min(f,e.cap)); if(d>0){ //v -> G[v][i].toにd流す e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s,int t){ int flow = 0; for(;;){ memset(used,0,sizeof(used)); int f = dfs(s,t,INF); if(f==0)return flow; flow += f; } } bool ad[2][70][70]; int S[70][70]; // 変える必要なし:0 (0->1):1 (1->0):2 int main() { int r,c; int cnt=0; int a; scanf("%d %d",&r,&c); for(int k=0;k<2;k++){ for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ scanf("%d",&a); if(a==1)ad[k][i][j]=true; else ad[k][i][j]=false; if(k==1){ if(ad[0][i][j]==true&&ad[1][i][j]==false){ S[i][j]=2;cnt++; }else if(ad[0][i][j]==false&&ad[1][i][j]==true){ S[i][j]=1;cnt++; }else S[i][j]=0; } } } } for(int i=0;i<r;i++){ for(int j=0;j<(c-1);j++){ if((S[i][j]==1&&S[i][j+1]==2) || (S[i][j]==2&&S[i][j+1]==1)){ if((i+j)%2==0)add_edge(i*c+j,i*c+j+1,1); else add_edge(i*c+j+1,i*c+j,1); } if((i+j)%2==0)add_edge(4900,i*c+j,1); else add_edge(i*c+j,4901,1); } } for(int i=0;i<r;i++){ if((c-1+i)%2==0)add_edge(4900,i*c+c-1,1); else add_edge(i*c+c-1,4901,1); } for(int i=0;i<c;i++){ for(int j=0;j<(r-1);j++){ if((S[j][i]==1&&S[j+1][i]==2) || (S[j][i]==2&&S[j+1][i]==1)){ if((i+j)%2==0)add_edge(j*c+i,(j+1)*c+i,1); else add_edge((j+1)*c+i,j*c+i,1); } } } int ans = max_flow(4900,4901); printf("%d\n",cnt-ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 天下一美術館 |
User | lyosika50 |
Language | C++14 (GCC 5.4.1) |
Score | 90 |
Code Size | 2372 Byte |
Status | AC |
Exec Time | 93 ms |
Memory | 1152 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:70:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d %d",&r,&c); ^ ./Main.cpp:74:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&a); ^
Judge Result
Set Name | small | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 40 / 40 | 50 / 50 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
small | 00_manual03.txt, 00_manual04.txt, 00_manual05.txt, 00_manual06.txt, 00_manual07.txt, 00_sample00.txt, 00_sample01.txt, 00_sample02.txt, 00_small100.txt, 00_small101.txt, 00_small102.txt, 00_small103.txt, 00_small104.txt, 00_small105.txt, 00_small106.txt, 00_small107.txt, 00_small108.txt, 00_small109.txt, 00_small110.txt, 00_small111.txt, 00_small112.txt, 00_small113.txt, 00_small114.txt, 00_small115.txt, 00_small116.txt, 00_small117.txt, 00_small118.txt, 00_small119.txt, 00_small120.txt, 00_small121.txt, 00_small122.txt, 00_small123.txt, 00_small124.txt, 00_small125.txt, 00_small126.txt, 00_small127.txt, 00_small128.txt, 00_small129.txt, 00_small130.txt, 00_small131.txt, 00_small132.txt, 00_small133.txt, 00_small134.txt, 00_small135.txt, 00_small136.txt, 00_small137.txt, 00_small138.txt, 00_small139.txt, 00_small140.txt, 00_small141.txt, 00_small142.txt, 00_small143.txt, 00_small144.txt, 00_small145.txt, 00_small146.txt, 00_small147.txt, 00_small148.txt, 00_small149.txt, 00_small150.txt, 00_small151.txt, 00_small152.txt, 00_small153.txt, 00_small154.txt, 00_small155.txt, 00_small156.txt, 00_small157.txt, 00_small158.txt |
All | 00_manual03.txt, 00_manual04.txt, 00_manual05.txt, 00_manual06.txt, 00_manual07.txt, 00_sample00.txt, 00_sample01.txt, 00_sample02.txt, 00_small100.txt, 00_small101.txt, 00_small102.txt, 00_small103.txt, 00_small104.txt, 00_small105.txt, 00_small106.txt, 00_small107.txt, 00_small108.txt, 00_small109.txt, 00_small110.txt, 00_small111.txt, 00_small112.txt, 00_small113.txt, 00_small114.txt, 00_small115.txt, 00_small116.txt, 00_small117.txt, 00_small118.txt, 00_small119.txt, 00_small120.txt, 00_small121.txt, 00_small122.txt, 00_small123.txt, 00_small124.txt, 00_small125.txt, 00_small126.txt, 00_small127.txt, 00_small128.txt, 00_small129.txt, 00_small130.txt, 00_small131.txt, 00_small132.txt, 00_small133.txt, 00_small134.txt, 00_small135.txt, 00_small136.txt, 00_small137.txt, 00_small138.txt, 00_small139.txt, 00_small140.txt, 00_small141.txt, 00_small142.txt, 00_small143.txt, 00_small144.txt, 00_small145.txt, 00_small146.txt, 00_small147.txt, 00_small148.txt, 00_small149.txt, 00_small150.txt, 00_small151.txt, 00_small152.txt, 00_small153.txt, 00_small154.txt, 00_small155.txt, 00_small156.txt, 00_small157.txt, 00_small158.txt, 01_large100.txt, 01_large101.txt, 01_large102.txt, 01_large103.txt, 01_large104.txt, 01_large105.txt, 01_large106.txt, 01_large107.txt, 01_large108.txt, 01_large1325.txt, 01_large1327.txt, 01_large1330.txt, 01_large1339.txt, 01_large1343.txt, 01_large1355.txt, 01_large1366.txt, 01_large1367.txt, 01_large1374.txt, 01_large1380.txt, 01_large1388.txt, 01_large1395.txt, 01_large1396.txt, 01_large1400.txt, 01_large1402.txt, 01_large1405.txt, 01_large1409.txt, 01_large1413.txt, 01_large1417.txt, 01_large1423.txt, 01_large1430.txt, 01_large1437.txt, 01_large1438.txt, 01_large1442.txt, 01_large1450.txt, 01_large1459.txt, 01_large1464.txt, 01_large1472.txt, 01_large1478.txt, 01_large1480.txt, 01_large1486.txt, 01_large1492.txt, 01_large1500.txt, 01_large1501.txt, 01_large1502.txt, 01_large1506.txt, 01_large157.txt, 01_large207.txt, 01_large507.txt, 01_large577.txt, 01_large591.txt, 01_large893.txt, 01_manual_L00.txt, 01_manual_L01.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_manual03.txt | AC | 1 ms | 384 KB |
00_manual04.txt | AC | 1 ms | 384 KB |
00_manual05.txt | AC | 1 ms | 384 KB |
00_manual06.txt | AC | 1 ms | 384 KB |
00_manual07.txt | AC | 1 ms | 384 KB |
00_sample00.txt | AC | 1 ms | 384 KB |
00_sample01.txt | AC | 1 ms | 384 KB |
00_sample02.txt | AC | 1 ms | 384 KB |
00_small100.txt | AC | 1 ms | 384 KB |
00_small101.txt | AC | 1 ms | 384 KB |
00_small102.txt | AC | 1 ms | 384 KB |
00_small103.txt | AC | 1 ms | 384 KB |
00_small104.txt | AC | 1 ms | 384 KB |
00_small105.txt | AC | 1 ms | 384 KB |
00_small106.txt | AC | 1 ms | 384 KB |
00_small107.txt | AC | 1 ms | 384 KB |
00_small108.txt | AC | 1 ms | 384 KB |
00_small109.txt | AC | 1 ms | 384 KB |
00_small110.txt | AC | 1 ms | 384 KB |
00_small111.txt | AC | 1 ms | 384 KB |
00_small112.txt | AC | 1 ms | 384 KB |
00_small113.txt | AC | 1 ms | 384 KB |
00_small114.txt | AC | 1 ms | 384 KB |
00_small115.txt | AC | 1 ms | 384 KB |
00_small116.txt | AC | 1 ms | 384 KB |
00_small117.txt | AC | 1 ms | 384 KB |
00_small118.txt | AC | 1 ms | 384 KB |
00_small119.txt | AC | 1 ms | 384 KB |
00_small120.txt | AC | 1 ms | 384 KB |
00_small121.txt | AC | 1 ms | 384 KB |
00_small122.txt | AC | 1 ms | 384 KB |
00_small123.txt | AC | 1 ms | 384 KB |
00_small124.txt | AC | 1 ms | 384 KB |
00_small125.txt | AC | 1 ms | 384 KB |
00_small126.txt | AC | 1 ms | 384 KB |
00_small127.txt | AC | 1 ms | 384 KB |
00_small128.txt | AC | 1 ms | 384 KB |
00_small129.txt | AC | 1 ms | 384 KB |
00_small130.txt | AC | 1 ms | 384 KB |
00_small131.txt | AC | 1 ms | 384 KB |
00_small132.txt | AC | 1 ms | 384 KB |
00_small133.txt | AC | 1 ms | 384 KB |
00_small134.txt | AC | 1 ms | 384 KB |
00_small135.txt | AC | 1 ms | 384 KB |
00_small136.txt | AC | 1 ms | 384 KB |
00_small137.txt | AC | 1 ms | 384 KB |
00_small138.txt | AC | 1 ms | 384 KB |
00_small139.txt | AC | 1 ms | 384 KB |
00_small140.txt | AC | 1 ms | 384 KB |
00_small141.txt | AC | 1 ms | 384 KB |
00_small142.txt | AC | 1 ms | 384 KB |
00_small143.txt | AC | 1 ms | 384 KB |
00_small144.txt | AC | 1 ms | 384 KB |
00_small145.txt | AC | 1 ms | 384 KB |
00_small146.txt | AC | 1 ms | 384 KB |
00_small147.txt | AC | 1 ms | 384 KB |
00_small148.txt | AC | 1 ms | 384 KB |
00_small149.txt | AC | 1 ms | 384 KB |
00_small150.txt | AC | 1 ms | 384 KB |
00_small151.txt | AC | 1 ms | 384 KB |
00_small152.txt | AC | 1 ms | 384 KB |
00_small153.txt | AC | 1 ms | 384 KB |
00_small154.txt | AC | 1 ms | 384 KB |
00_small155.txt | AC | 1 ms | 384 KB |
00_small156.txt | AC | 1 ms | 384 KB |
00_small157.txt | AC | 1 ms | 384 KB |
00_small158.txt | AC | 1 ms | 384 KB |
01_large100.txt | AC | 1 ms | 384 KB |
01_large101.txt | AC | 1 ms | 384 KB |
01_large102.txt | AC | 1 ms | 384 KB |
01_large103.txt | AC | 2 ms | 384 KB |
01_large104.txt | AC | 1 ms | 384 KB |
01_large105.txt | AC | 3 ms | 512 KB |
01_large106.txt | AC | 1 ms | 384 KB |
01_large107.txt | AC | 1 ms | 384 KB |
01_large108.txt | AC | 9 ms | 1024 KB |
01_large1325.txt | AC | 40 ms | 768 KB |
01_large1327.txt | AC | 13 ms | 1152 KB |
01_large1330.txt | AC | 10 ms | 1152 KB |
01_large1339.txt | AC | 39 ms | 768 KB |
01_large1343.txt | AC | 11 ms | 1152 KB |
01_large1355.txt | AC | 12 ms | 1024 KB |
01_large1366.txt | AC | 37 ms | 896 KB |
01_large1367.txt | AC | 39 ms | 768 KB |
01_large1374.txt | AC | 38 ms | 896 KB |
01_large1380.txt | AC | 19 ms | 896 KB |
01_large1388.txt | AC | 76 ms | 896 KB |
01_large1395.txt | AC | 71 ms | 768 KB |
01_large1396.txt | AC | 11 ms | 1152 KB |
01_large1400.txt | AC | 10 ms | 1024 KB |
01_large1402.txt | AC | 53 ms | 896 KB |
01_large1405.txt | AC | 38 ms | 768 KB |
01_large1409.txt | AC | 39 ms | 768 KB |
01_large1413.txt | AC | 10 ms | 1024 KB |
01_large1417.txt | AC | 24 ms | 1024 KB |
01_large1423.txt | AC | 52 ms | 768 KB |
01_large1430.txt | AC | 76 ms | 896 KB |
01_large1437.txt | AC | 53 ms | 768 KB |
01_large1438.txt | AC | 11 ms | 1152 KB |
01_large1442.txt | AC | 10 ms | 1152 KB |
01_large1450.txt | AC | 49 ms | 896 KB |
01_large1459.txt | AC | 26 ms | 1024 KB |
01_large1464.txt | AC | 51 ms | 896 KB |
01_large1472.txt | AC | 64 ms | 896 KB |
01_large1478.txt | AC | 53 ms | 896 KB |
01_large1480.txt | AC | 11 ms | 1024 KB |
01_large1486.txt | AC | 54 ms | 896 KB |
01_large1492.txt | AC | 30 ms | 896 KB |
01_large1500.txt | AC | 42 ms | 896 KB |
01_large1501.txt | AC | 17 ms | 1024 KB |
01_large1502.txt | AC | 32 ms | 768 KB |
01_large1506.txt | AC | 33 ms | 896 KB |
01_large157.txt | AC | 39 ms | 1024 KB |
01_large207.txt | AC | 12 ms | 1024 KB |
01_large507.txt | AC | 93 ms | 1024 KB |
01_large577.txt | AC | 82 ms | 1024 KB |
01_large591.txt | AC | 79 ms | 1024 KB |
01_large893.txt | AC | 12 ms | 1152 KB |
01_manual_L00.txt | AC | 2 ms | 640 KB |
01_manual_L01.txt | AC | 2 ms | 640 KB |