답안 #78651 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
78651	2018-10-06T20:26:21 Z	duality	007 (CEOI14_007)	C++11	30 / 100	334 ms	16680 KB

#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 ----------

vi adjList[200000];
int dist1[200000],dist2[200000];
queue<int> Q;
int main() {
    int i;
    int N,M;
    int s,d,a,b,u,v;
    scanf("%d %d",&N,&M);
    scanf("%d %d %d %d",&s,&d,&a,&b);
    s--,d--,a--,b--;
    for (i = 0; i < M; i++) {
        scanf("%d %d",&u,&v);
        u--,v--;
        adjList[u].pb(v);
        adjList[v].pb(u);
    }

    fill(dist1,dist1+N,-1);
    dist1[a] = 0;
    Q.push(a);
    while (!Q.empty()) {
        u = Q.front();
        Q.pop();

        for (i = 0; i < adjList[u].size(); i++) {
            v = adjList[u][i];
            if (dist1[v] == -1) {
                dist1[v] = dist1[u]+1;
                Q.push(v);
            }
        }
    }
    fill(dist2,dist2+N,-1);
    dist2[b] = 0;
    Q.push(b);
    while (!Q.empty()) {
        u = Q.front();
        Q.pop();

        for (i = 0; i < adjList[u].size(); i++) {
            v = adjList[u][i];
            if (dist2[v] == -1) {
                dist2[v] = dist2[u]+1;
                Q.push(v);
            }
        }
    }
    int ans = max(min(dist1[d]-dist1[s],dist2[d]-dist2[s]),-1);
    if (dist1[s] != dist2[s]) {
        if (dist1[s] < dist2[s]) {
            if (dist2[d] == ans+dist1[s]) ans--;
        }
        else {
            if (dist1[d] == ans+dist2[s]) ans--;
        }
        printf("%d\n",max(ans,-1));
    }
    else printf("%d\n",max(min(dist1[d]-dist1[s],dist2[d]-dist2[s])-1,-1));

    return 0;
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:82:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
007.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
007.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&M);
     ~~~~~^~~~~~~~~~~~~~~
007.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d",&s,&d,&a,&b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&u,&v);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
9.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	6 ms	4988 KB	Output is correct
3	Partially correct	6 ms	5160 KB	Partially correct
4	Correct	7 ms	5160 KB	Output is correct
5	Correct	6 ms	5380 KB	Output is correct
6	Partially correct	6 ms	5380 KB	Partially correct
7	Partially correct	6 ms	5380 KB	Partially correct
8	Correct	6 ms	5380 KB	Output is correct
9	Partially correct	6 ms	5380 KB	Partially correct
10	Correct	6 ms	5380 KB	Output is correct
11	Partially correct	6 ms	5380 KB	Partially correct
12	Correct	6 ms	5380 KB	Output is correct
13	Partially correct	6 ms	5380 KB	Partially correct
14	Correct	6 ms	5380 KB	Output is correct
15	Partially correct	7 ms	5380 KB	Partially correct
16	Correct	6 ms	5380 KB	Output is correct
17	Correct	6 ms	5380 KB	Output is correct
18	Correct	6 ms	5380 KB	Output is correct
19	Partially correct	7 ms	5380 KB	Partially correct
20	Partially correct	6 ms	5380 KB	Partially correct
21	Correct	6 ms	5380 KB	Output is correct
22	Partially correct	6 ms	5380 KB	Partially correct
23	Partially correct	6 ms	5380 KB	Partially correct
24	Correct	6 ms	5380 KB	Output is correct

Subtask #2
21.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	30 ms	7036 KB	Partially correct
2	Correct	38 ms	7548 KB	Output is correct
3	Partially correct	30 ms	7548 KB	Partially correct
4	Correct	43 ms	7680 KB	Output is correct
5	Correct	30 ms	7680 KB	Output is correct
6	Correct	29 ms	7680 KB	Output is correct
7	Partially correct	34 ms	7680 KB	Partially correct
8	Partially correct	34 ms	7680 KB	Partially correct
9	Correct	49 ms	7680 KB	Output is correct
10	Partially correct	190 ms	11908 KB	Partially correct
11	Correct	62 ms	11908 KB	Output is correct
12	Partially correct	81 ms	11908 KB	Partially correct
13	Correct	69 ms	11908 KB	Output is correct
14	Correct	91 ms	11908 KB	Output is correct
15	Partially correct	119 ms	11908 KB	Partially correct
16	Correct	107 ms	11908 KB	Output is correct
17	Partially correct	80 ms	11908 KB	Partially correct
18	Correct	77 ms	11908 KB	Output is correct
19	Partially correct	130 ms	11908 KB	Partially correct
20	Correct	256 ms	13584 KB	Output is correct
21	Correct	110 ms	13584 KB	Output is correct
22	Partially correct	104 ms	13584 KB	Partially correct
23	Correct	115 ms	13584 KB	Output is correct
24	Partially correct	118 ms	13584 KB	Partially correct
25	Correct	107 ms	13584 KB	Output is correct
26	Correct	103 ms	13584 KB	Output is correct
27	Partially correct	187 ms	13584 KB	Partially correct
28	Partially correct	115 ms	13584 KB	Partially correct
29	Partially correct	157 ms	13584 KB	Partially correct
30	Correct	265 ms	14320 KB	Output is correct
31	Correct	129 ms	14320 KB	Output is correct
32	Partially correct	118 ms	14320 KB	Partially correct
33	Correct	114 ms	14320 KB	Output is correct
34	Correct	147 ms	14320 KB	Output is correct
35	Correct	109 ms	14320 KB	Output is correct
36	Correct	117 ms	14320 KB	Output is correct
37	Correct	141 ms	14320 KB	Output is correct
38	Partially correct	130 ms	14320 KB	Partially correct
39	Partially correct	153 ms	14320 KB	Partially correct
40	Correct	204 ms	14332 KB	Output is correct
41	Partially correct	334 ms	16680 KB	Partially correct

답안 #78651

Compilation message

Subtask #1 9.0 / 30.0

Subtask #2 21.0 / 70.0

Subtask #1
9.0 / 30.0

Subtask #2
21.0 / 70.0