oj.uz

Submission #35007

# Submission time Handle Problem Language Result Execution time Memory
35007 2017-11-17T09:21:32 Z long10024070 스파이 (JOI13_spy) C++11
30 / 100
 2000 ms 24520 KB 
#define Link ""

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

#define TASK "SPY"

using namespace std;

void OpenFile()
{
    freopen(".INP","r",stdin);
    freopen(".OUT","w",stdout);
}

const int maxn = 2e3 + 1;
int n,m,p[2][maxn],res[maxn];
vector <int> c[2][maxn];

int FastIn()
{
    int res = 0;
    register char c = getchar();
    while (c < '0' || '9' < c) c = getchar();
    while ('0' <= c && c <= '9') res = res * 10 + c - '0', c = getchar();
    return res;
}

inline void writeln(int x)
{

    char buffor[21];
    register int i=0;
    int neg=0;
    if (x<0) {
        neg=1;
        x= -x;
    }
    do {
        buffor[i++]=(x%10)+'0';
        x/=10;
    }
    while(x);
    i--;
    if (neg) putchar('-');
    while(i>=0) putchar(buffor[i--]);
    putchar('\n');
}

void Enter()
{
    n = FastIn();
    m = FastIn();
    for (int i=1;i<=n;++i) {
        p[0][i] = FastIn();
        p[1][i] = FastIn();
    }
}

void DFS(int t, int i, int u)
{
    if (u == 0)
        return;
    c[t][u].push_back(i);
    DFS(t,i,p[t][u]);
}

void Init()
{
    for (int i=1;i<=n;++i) {
        DFS(0,i,i);
        DFS(1,i,i);
    }
    for (int i=1;i<=n;++i) {
        sort(c[0][i].begin(),c[0][i].end());
        sort(c[1][i].begin(),c[1][i].end());
    }
}

void Solve()
{
    for (;m>0;--m) {
        int R,S;
        R = FastIn();
        S = FastIn();
        int i = 0;
        int j = 0;
        while (i < c[0][R].size() && j < c[1][S].size()) {
            if (c[0][R][i] == c[1][S][j]) {
                ++res[c[1][S][j]];
                ++i;
                ++j;
            }
            else
                if (c[0][R][i] < c[1][S][j])
                    ++i;
                else
                    ++j;
        }
    }
    for (int i=1;i<=n;++i)
        writeln(res[i]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    //OpenFile();

    Enter();
    Init();
    Solve();
}

Compilation message

spy.cpp: In function 'void Solve()':
spy.cpp:90:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i < c[0][R].size() && j < c[1][S].size()) {
                  ^
spy.cpp:90:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i < c[0][R].size() && j < c[1][S].size()) {
                                        ^
spy.cpp: In function 'void OpenFile()':
spy.cpp:14:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(".INP","r",stdin);
                              ^
spy.cpp:15:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(".OUT","w",stdout);
                               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2560 KB Output is correct
2 Correct 0 ms 2560 KB Output is correct
3 Correct 0 ms 2296 KB Output is correct
4 Correct 0 ms 2296 KB Output is correct
5 Correct 0 ms 2296 KB Output is correct
6 Correct 0 ms 2296 KB Output is correct
7 Correct 0 ms 2428 KB Output is correct
8 Correct 0 ms 2296 KB Output is correct
9 Correct 0 ms 2296 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 24520 KB Output is correct
2 Correct 233 ms 24516 KB Output is correct
3 Correct 3 ms 2428 KB Output is correct
4 Correct 6 ms 2428 KB Output is correct
5 Correct 3 ms 2696 KB Output is correct
6 Correct 19 ms 2692 KB Output is correct
7 Correct 29 ms 6540 KB Output is correct
8 Correct 3 ms 2824 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 24520 KB Execution timed out
2 Halted 0 ms 0 KB -