답안 #78652 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
78652	2018-10-06T20:29:00 Z	duality	007 (CEOI14_007)	C++11	30 / 100	331 ms	16984 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 {
        if (dist1[d] != dist2[d]) printf("%d\n",ans);
        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	5120 KB	Output is correct
3	Partially correct	6 ms	5120 KB	Partially correct
4	Correct	6 ms	5280 KB	Output is correct
5	Correct	6 ms	5280 KB	Output is correct
6	Partially correct	6 ms	5280 KB	Partially correct
7	Partially correct	6 ms	5296 KB	Partially correct
8	Correct	6 ms	5296 KB	Output is correct
9	Partially correct	6 ms	5296 KB	Partially correct
10	Correct	6 ms	5296 KB	Output is correct
11	Correct	6 ms	5296 KB	Output is correct
12	Correct	6 ms	5352 KB	Output is correct
13	Partially correct	6 ms	5352 KB	Partially correct
14	Correct	6 ms	5352 KB	Output is correct
15	Partially correct	6 ms	5352 KB	Partially correct
16	Correct	6 ms	5352 KB	Output is correct
17	Correct	6 ms	5352 KB	Output is correct
18	Correct	6 ms	5352 KB	Output is correct
19	Partially correct	6 ms	5352 KB	Partially correct
20	Partially correct	6 ms	5352 KB	Partially correct
21	Correct	6 ms	5352 KB	Output is correct
22	Partially correct	6 ms	5352 KB	Partially correct
23	Partially correct	6 ms	5352 KB	Partially correct
24	Correct	6 ms	5352 KB	Output is correct

Subtask #2
21.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	27 ms	6880 KB	Partially correct
2	Correct	37 ms	8032 KB	Output is correct
3	Partially correct	32 ms	8032 KB	Partially correct
4	Correct	36 ms	8064 KB	Output is correct
5	Correct	29 ms	8064 KB	Output is correct
6	Correct	28 ms	8064 KB	Output is correct
7	Partially correct	33 ms	8064 KB	Partially correct
8	Partially correct	32 ms	8064 KB	Partially correct
9	Correct	47 ms	8064 KB	Output is correct
10	Partially correct	184 ms	12476 KB	Partially correct
11	Correct	59 ms	12476 KB	Output is correct
12	Partially correct	81 ms	12476 KB	Partially correct
13	Correct	72 ms	12476 KB	Output is correct
14	Correct	54 ms	12476 KB	Output is correct
15	Partially correct	73 ms	12476 KB	Partially correct
16	Correct	95 ms	12476 KB	Output is correct
17	Partially correct	70 ms	12476 KB	Partially correct
18	Correct	70 ms	12476 KB	Output is correct
19	Partially correct	123 ms	12476 KB	Partially correct
20	Correct	229 ms	14068 KB	Output is correct
21	Correct	107 ms	14068 KB	Output is correct
22	Partially correct	99 ms	14068 KB	Partially correct
23	Correct	102 ms	14068 KB	Output is correct
24	Partially correct	105 ms	14068 KB	Partially correct
25	Correct	101 ms	14068 KB	Output is correct
26	Correct	95 ms	14068 KB	Output is correct
27	Partially correct	132 ms	14068 KB	Partially correct
28	Partially correct	178 ms	14068 KB	Partially correct
29	Partially correct	165 ms	14068 KB	Partially correct
30	Correct	252 ms	14552 KB	Output is correct
31	Correct	131 ms	14552 KB	Output is correct
32	Partially correct	120 ms	14552 KB	Partially correct
33	Correct	117 ms	14552 KB	Output is correct
34	Correct	144 ms	14552 KB	Output is correct
35	Correct	116 ms	14552 KB	Output is correct
36	Correct	126 ms	14552 KB	Output is correct
37	Correct	143 ms	14552 KB	Output is correct
38	Partially correct	139 ms	14552 KB	Partially correct
39	Partially correct	156 ms	14552 KB	Partially correct
40	Correct	231 ms	14788 KB	Output is correct
41	Partially correct	331 ms	16984 KB	Partially correct

답안 #78652

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