oj.uz

Submission #25938

# Submission time Handle Problem Language Result Execution time Memory
25938 2017-06-25T07:27:11 Z 시제연(#1089) The Forest of Fangorn (CEOI14_fangorn) C++
0 / 100
 0 ms 1852 KB 
#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

int n, c, w, h;
pll tree[2100];
pll camp[10100];
int lab[10100][2100];
pll st;

vector<pll> tec, oec;

ll ccw (pll a, pll b) {return a.x*b.y-a.y*b.x;}

int wh(pll a) {
    if (a.x>0||a.x==0&&a.y>0) return 0;
    return 1;
}

bool cmpp(pll A, pll B) {
    return wh(A)!=wh(B)?wh(A)<wh(B):ccw(A,B)>0;
}

pll operator - (pll &A, pll &B) {
    return pll(A.x-B.x,A.y-B.y);
}

bool cmp(int a, int b) {
    return cmpp(oec[a],oec[b]);
}

int ord[10100];
void solve(int idx) {
    int i, j;
    tec.clear();
    oec.clear();
    for (i=0;i<n;i++) {
        if (i==idx) continue;
        tec.push_back(tree[idx]-tree[i]);
    }
    for (i=0;i<c;i++) oec.push_back(camp[i]-tree[idx]);
    oec.push_back(st-tree[idx]);
    for (i=0;i<=c;i++) ord[i] = i;
    sort(tec.begin(),tec.end(),cmpp);
    sort(ord,ord+c+1,cmp);
    i=j=0;
    while(i<tec.size()||j<=c) {
        if (i==tec.size()) lab[ord[j++]][idx] = i%(n-1);
        else if (j==c+1) i++;
        else if (cmpp(tec[i],oec[ord[j]])) i++;
        else lab[ord[j++]][idx] = i%(n-1);
    }
}

int main() {
    int i, j;

    scanf("%d%d",&w,&h);
    scanf("%lld%lld\n",&st.x,&st.y);
    scanf("%d",&c);
    for (i=0;i<c;i++) scanf("%d%d",&camp[i].x,&camp[i].y);
    scanf("%d",&n);
    for (i=0;i<n;i++) scanf("%d%d",&tree[i].x,&tree[i].y);
    for (i=0;i<n;i++) solve(i);

    vector<int> res;
    for (i=0;i<c;i++) {
        bool flag = true;
        for (j=0;j<n;j++) if (lab[i][j]!=lab[c][j]) flag = false;
        if (flag) res.push_back(i+1);
    }
    printf("%d\n",res.size());
    for (i=0;i<res.size();i++) printf("%d ",res[i]);
    printf("\n");

    return 0;
}

Compilation message

fangorn.cpp: In function 'int wh(pll)':
fangorn.cpp:22:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (a.x>0||a.x==0&&a.y>0) return 0;
                      ^
fangorn.cpp: In function 'void solve(int)':
fangorn.cpp:53:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i<tec.size()||j<=c) {
            ^
fangorn.cpp:54:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i==tec.size()) lab[ord[j++]][idx] = i%(n-1);
              ^
fangorn.cpp: In function 'int main()':
fangorn.cpp:67:57: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     for (i=0;i<c;i++) scanf("%d%d",&camp[i].x,&camp[i].y);
                                                         ^
fangorn.cpp:67:57: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
fangorn.cpp:69:57: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     for (i=0;i<n;i++) scanf("%d%d",&tree[i].x,&tree[i].y);
                                                         ^
fangorn.cpp:69:57: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
fangorn.cpp:78:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n",res.size());
                             ^
fangorn.cpp:79:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<res.size();i++) printf("%d ",res[i]);
               ^
fangorn.cpp:64:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&w,&h);
                        ^
fangorn.cpp:65:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld\n",&st.x,&st.y);
                                    ^
fangorn.cpp:66:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&c);
                   ^
fangorn.cpp:67:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i=0;i<c;i++) scanf("%d%d",&camp[i].x,&camp[i].y);
                                                          ^
fangorn.cpp:68:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
fangorn.cpp:69:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i=0;i<n;i++) scanf("%d%d",&tree[i].x,&tree[i].y);
                                                          ^

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -