제출 #131278

#제출 시각아이디문제언어결과실행 시간메모리
131278dualityCats or Dogs (JOI18_catdog)C++11
38 / 100
3046 ms12000 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- #include "catdog.h" int n; vi adjList[100000]; int parent[100000],dp[100000][2]; int curr[100000]; int doDFS(int u,int p) { int i; parent[u] = p; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (v != p) doDFS(v,u); } return 0; } void initialize(int N,vector<int> A,vector<int> B) { int i; n = N; for (i = 0; i < N-1; i++) { A[i]--,B[i]--; adjList[A[i]].pb(B[i]); adjList[B[i]].pb(A[i]); } doDFS(0,-1); } int update(int u) { int i; while (u != -1) { dp[u][0] = dp[u][1] = 0; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (v != parent[u]) { dp[u][0] += min(dp[v][0],dp[v][1]+1); dp[u][1] += min(dp[v][1],dp[v][0]+1); } } if (curr[u] == 1) dp[u][1] = 1e9; else if (curr[u] == 2) dp[u][0] = 1e9; u = parent[u]; } return 0; } int cat(int v) { v--,curr[v] = 1,update(v); return min(dp[0][0],dp[0][1]); } int dog(int v) { v--,curr[v] = 2,update(v); return min(dp[0][0],dp[0][1]); } int neighbor(int v) { v--,curr[v] = 0,update(v); return min(dp[0][0],dp[0][1]); }

컴파일 시 표준 에러 (stderr) 메시지

catdog.cpp: In function 'int doDFS(int, int)':
catdog.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
catdog.cpp: In function 'int update(int)':
catdog.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...