oj.uz

Submission #25458

# Submission time Handle Problem Language Result Execution time Memory
25458 2017-06-22T08:17:02 Z 시제연(#1067) Synchronization (JOI13_synchronization) C++
60 / 100
 463 ms 30072 KB 
#include <bits/stdc++.h>
#define a first
#define b second

using namespace std;

typedef pair<int,int> pii;

struct idxtree {
    int tree[270000];
    int key = 131072, type;
    idxtree(int t) {
        type = t;
        int ival = ((t)?987654321:-987654321);
        for (int i=0;i<key*2;i++) tree[i] = ival;
    }
    int mer(int a, int b) {
        if (type) return min(a,b);
        return max(a,b);
    }
    void upd(int s, int e, int val) {
        s += key; e += key;
        while(s<=e) {
            if (s&1) tree[s] = mer(tree[s],val);
            if (~e&1) tree[e] = mer(tree[e],val);
            s = (s+1)>>1; e = (e-1)>>1;
        }
    }
    int getv(int idx) {
        idx += key;
        int res = ((type)?987654321:-987654321);
        while(idx>0) {
            res = mer(res,tree[idx]);
            idx>>=1;
        }
        return res;
    }
} maxt(0), mint(1);

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));
    }
}

set<pii> se;
int main() {
    int i;

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

    bool flag = true;
    scanf("%d%d%d",&n,&m,&q);
    for (i=0;i<n-1;i++) {
        int a, b;
        scanf("%d%d",&a,&b);
        a--;b--;
        if (a!=i||b!=i+1) flag = false;
        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 (q==1) {
        dfs(que[0],-1,m);
        int cnt = 0;
        for (int j=0;j<n;j++) if (visit[j]) cnt++;
        printf("%d\n",cnt);
    }
    else if (flag) {
        for (i=0;i<n;i++) maxt.upd(i,i,i);
        for (i=0;i<n;i++) mint.upd(i,i,i);
        for (i=0;i<n;i++) se.insert(pii(i,i));
        for (i=0;i<n-1;i++) on[i] = false;
        for (i=0;i<m;i++) {
            if (on[cha[i]]) {
                set<pii>::iterator it = --se.lower_bound(pii(cha[i],m+10));
                pii tmp = (*it);
                se.erase(it);
                se.insert(pii(tmp.first,cha[i]));
                se.insert(pii(cha[i]+1,tmp.second));
            }
            else {
                set<pii>::iterator it = se.lower_bound(pii(cha[i],m+10));
                set<pii>::iterator pt = --it; ++it;
                mint.upd(it->first,it->second,mint.getv(cha[i]));
                maxt.upd(pt->first,pt->second,maxt.getv(cha[i]+1));
                pii tmp = pii(pt->first,it->second);
                se.erase(it); se.erase(pt);
                se.insert(tmp);
            }
            on[cha[i]] = !on[cha[i]];
        }
        for (i=0;i<q;i++) {
            printf("%d\n",maxt.getv(que[i])-mint.getv(que[i])+1);
        }
    }

    return 0;
}

Compilation message

synchronization.cpp:11:15: warning: non-static data member initializers only available with -std=c++11 or -std=gnu++11
     int key = 131072, type;
               ^
synchronization.cpp: In function 'void dfs(int, int, int)':
synchronization.cpp:55: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:72: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:75: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:85:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&cha[i]);
                            ^
synchronization.cpp:93: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 6 ms 13716 KB Output is correct
2 Correct 3 ms 13716 KB Output is correct
3 Correct 3 ms 13716 KB Output is correct
4 Correct 0 ms 13716 KB Output is correct
5 Correct 3 ms 13716 KB Output is correct
6 Correct 3 ms 13848 KB Output is correct
7 Correct 9 ms 14640 KB Output is correct
8 Correct 9 ms 14640 KB Output is correct
9 Correct 13 ms 14640 KB Output is correct
10 Correct 149 ms 22956 KB Output is correct
11 Correct 156 ms 22956 KB Output is correct
12 Correct 153 ms 22824 KB Output is correct
13 Correct 133 ms 23780 KB Output is correct
14 Correct 173 ms 23352 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 27908 KB Output is correct
2 Correct 69 ms 26040 KB Output is correct
3 Correct 83 ms 30072 KB Output is correct
4 Correct 76 ms 29052 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13716 KB Output is correct
2 Correct 0 ms 13716 KB Output is correct
3 Correct 6 ms 13716 KB Output is correct
4 Correct 3 ms 13716 KB Output is correct
5 Correct 0 ms 13716 KB Output is correct
6 Correct 3 ms 13848 KB Output is correct
7 Correct 26 ms 15168 KB Output is correct
8 Correct 449 ms 27444 KB Output is correct
9 Correct 463 ms 27444 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 27444 KB Output is correct
2 Correct 169 ms 27708 KB Output is correct
3 Correct 173 ms 27840 KB Output is correct
4 Correct 166 ms 27840 KB Output is correct

Subtask #5
0 / 40.0

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