oj.uz

Submission #25451

# Submission time Handle Problem Language Result Execution time Memory
25451 2017-06-22T07:53:05 Z 시제연(#1067) Synchronization (JOI13_synchronization) C++
30 / 100
 243 ms 27956 KB 
#include <bits/stdc++.h>
#define a first
#define b second

using namespace std;

typedef pair<int,int> pii;

int n, m, q;
vector<int> lis[100100];
vector<int> id[100100];
pii edg[100100];
int cha[200100];
int que[100100];
int last[100100];
bool on[100100];

vector<pii> ran[100100];
bool visit[100100];

void dfs(int here, int p, int tim) {
    int i;
    visit[here] = true;
    for (i=0;i<lis[here].size();i++) {
        int there = lis[here][i];
        int idx = id[here][i];
        if (there==p) continue;
        int nim = lower_bound(ran[idx].begin(),ran[idx].end(),pii(tim,m+10))-ran[idx].begin()-1;
        if (nim<0) continue;
        dfs(there,here,min(tim,ran[idx][nim].second));
    }
}

int main() {
    int i;

    //freopen("input","r",stdin);

    scanf("%d%d%d",&n,&m,&q);
    for (i=0;i<n-1;i++) {
        int a, b;
        scanf("%d%d",&a,&b);
        a--;b--;
        lis[a].push_back(b);
        lis[b].push_back(a);
        id[a].push_back(i);
        id[b].push_back(i);
        edg[i] = pii(a,b);
    }
    for (i=0;i<m;i++) {
        scanf("%d",&cha[i]);
        cha[i]--;
        if (on[cha[i]]) ran[cha[i]].push_back(pii(last[cha[i]],i));
        on[cha[i]] = !on[cha[i]];
        last[cha[i]] = i;
    }
    for (i=0;i<n-1;i++) if (on[i]) ran[i].push_back(pii(last[i],m));
    for (i=0;i<q;i++) {
        scanf("%d",&que[i]);
        que[i]--;
        if (i==0) {
            dfs(que[i],-1,m);
            int cnt = 0;
            for (int j=0;j<n;j++) if (visit[j]) cnt++;
            printf("%d\n",cnt);
        }
    }

    return 0;
}

Compilation message

synchronization.cpp: In function 'void dfs(int, int, int)':
synchronization.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[here].size();i++) {
               ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:39:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&q);
                             ^
synchronization.cpp:42:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
                            ^
synchronization.cpp:51:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&cha[i]);
                            ^
synchronization.cpp:59:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&que[i]);
                            ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11604 KB Output is correct
2 Correct 0 ms 11604 KB Output is correct
3 Correct 6 ms 11604 KB Output is correct
4 Correct 0 ms 11604 KB Output is correct
5 Correct 3 ms 11604 KB Output is correct
6 Correct 3 ms 11736 KB Output is correct
7 Correct 19 ms 12528 KB Output is correct
8 Correct 13 ms 12528 KB Output is correct
9 Correct 6 ms 12528 KB Output is correct
10 Correct 223 ms 20844 KB Output is correct
11 Correct 243 ms 20844 KB Output is correct
12 Correct 156 ms 20712 KB Output is correct
13 Correct 136 ms 21668 KB Output is correct
14 Correct 226 ms 21240 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 25800 KB Output is correct
2 Correct 99 ms 23920 KB Output is correct
3 Correct 79 ms 27956 KB Output is correct
4 Correct 66 ms 26944 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 20712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -