oj.uz

답안 #25457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25457 2017-06-22T08:16:13 Z 시제연(#1067) 동기화 (JOI13_synchronization) C++
30 / 100
 446 ms 27908 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[i],-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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 13716 KB Output is correct
2 Correct 0 ms 13716 KB Output is correct
3 Incorrect 0 ms 13716 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 27908 KB Output is correct
2 Correct 113 ms 27776 KB Output is correct
3 Incorrect 76 ms 23088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 13716 KB Output is correct
2 Correct 6 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 23 ms 15168 KB Output is correct
8 Correct 376 ms 27444 KB Output is correct
9 Correct 446 ms 27444 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 443 ms 27444 KB Output is correct
2 Correct 193 ms 27708 KB Output is correct
3 Correct 143 ms 27840 KB Output is correct
4 Correct 163 ms 27840 KB Output is correct

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 13716 KB Output isn't correct
2 Halted 0 ms 0 KB -