Submission #3221854
Source Code Expand
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPr(i,n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define VSCD(v,N) REP(i,N){int x; SCD(x); v.PB(x);}
#define VSCLLD(v,N) REP(i,N){long long x; SCLLD(x); v.PB(x);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
////////////////////////////////////////////////////////////////////
typedef pair<ll,ll> PLL;
typedef pair<PLL,PLL> PLLL;
struct UnionFind {
vector<int> data;
UnionFind(int size) : data(size,-1) { }
int root(int x){
if (data[x] < 0) return x;
else return data[x] = root(data[x]);
}
int size(int x){
return -data[root(x)];
}
bool isConnect(int x,int y){
return root(x) == root(y);
}
bool connect(int x , int y){
x = root(x);
y = root(y);
if(x==y) return false;
if(data[x] > data[y]){
x ^= y;
y ^= x;
x ^= y;
}
data[x] = data[x] + data[y]; // membersize++
data[y] = x;
return true;
}
};
UnionFind U(10002);
int main(){
ll ans = 0;
int H,W; SCD2(H,W);
int Sx,Sy; SCD2(Sx,Sy);
int Gx,Gy; SCD2(Gx,Gy);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
static ll P[102][102] = {};
FORq(j,1,H){
FORq(i,1,W){
SCD(P[i][j]);
ans += P[i][j];
}
}
int selected = 0;
priority_queue<pair<ll,PLLL> >Q;
FORq(j,1,H){
FORq(i,1,W){
PII start = MP(i,j);
PII endd = MP(i+1,j);
ll cost = P[i][j] * P[i+1][j];
Q.push(MP(cost,MP(start,endd)));
endd = MP(i,j+1);
cost = P[i][j] * P[i][j+1];
Q.push(MP(cost,MP(start,endd)));
}
}
while((selected <= W*H-2) and (!Q.empty())){
pair<ll,PLLL> now = Q.top(); Q.pop();
ll ncost = now.first;
PLL A = now.second.first;
PLL B = now.second.second;
int a = W * (A.second - 1) + (A.first);
int b = W * (B.second - 1) + (B.first);
if (U.isConnect(a,b) == false) {
U.connect(a,b);
selected++;
ans += ncost;
}
}
PRINTLLD(ans);
}
Submission Info
Submission Time
2018-09-18 23:09:34+0900
Task
D - Game on a Grid
User
Lithium
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2895 Byte
Status
RE
Exec Time
119 ms
Memory
1784 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:6:29: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘ll* {aka long long int*}’ [-Wformat=]
#define SCD(n) scanf("%d",&n)
^
./Main.cpp:85:4: note: in expansion of macro ‘SCD’
SCD(P[i][j]);
^
./Main.cpp:75:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int H,W; SCD2(H,W);
^
./Main.cpp:76:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int Sx,Sy; SCD2(Sx,Sy);
^
./Main.cpp:77:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int Gx,Gy; SCD2(Gx,Gy);
^
./Main.cpp:85:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wu...
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 100
Status
Set Name
Test Cases
Sample
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt
Case Name
Status
Exec Time
Memory
subtask0_sample_01.txt
AC
1 ms
256 KB
subtask0_sample_02.txt
AC
1 ms
256 KB
subtask0_sample_03.txt
AC
1 ms
256 KB
subtask1_01.txt
AC
1 ms
256 KB
subtask1_02.txt
AC
1 ms
256 KB
subtask1_03.txt
AC
1 ms
256 KB
subtask1_04.txt
AC
1 ms
256 KB
subtask1_05.txt
AC
1 ms
256 KB
subtask1_06.txt
AC
1 ms
256 KB
subtask1_07.txt
RE
119 ms
1784 KB
subtask1_08.txt
RE
103 ms
1784 KB
subtask1_09.txt
RE
103 ms
1784 KB
subtask1_10.txt
RE
103 ms
1784 KB
subtask1_11.txt
RE
103 ms
1784 KB
subtask1_12.txt
RE
103 ms
1784 KB
subtask1_13.txt
RE
102 ms
1784 KB
subtask1_14.txt
RE
102 ms
1784 KB
subtask1_15.txt
RE
103 ms
1784 KB
subtask1_16.txt
AC
6 ms
1784 KB
subtask1_17.txt
AC
1 ms
384 KB
subtask1_18.txt
AC
1 ms
384 KB
subtask1_19.txt
AC
1 ms
384 KB
subtask1_20.txt
RE
103 ms
1784 KB
subtask1_21.txt
RE
103 ms
1784 KB
subtask1_22.txt
RE
103 ms
1784 KB
subtask1_23.txt
RE
104 ms
1784 KB
subtask1_24.txt
AC
1 ms
256 KB
subtask1_25.txt
AC
1 ms
256 KB
subtask1_26.txt
AC
1 ms
384 KB
subtask1_27.txt
AC
1 ms
256 KB
subtask1_28.txt
AC
1 ms
384 KB
subtask1_29.txt
AC
1 ms
256 KB