oj.uz

Submission #42684

# Submission time Handle Problem Language Result Execution time Memory
42684 2018-03-02T15:53:22 Z bash Birthday gift (IZhO18_treearray) C++14
0 / 100
 38 ms 42744 KB 
/**
SXR0aXAkI0JwbXptI3FhI3Z3I293bCNqY2IjUG0jMCNicG0jVHFkcXZvLyNCcG0jQW10bjBhY2phcWFicXZvLyNNYm16dml0MSNWdyNhdGN1am16I2tpdiNhbXF9bSNQcXUjVnd6I0F0bW14MSNQcWEjaXptI2l0dCNicHF2b2EjUXYjYnBtI3BtaWRtdmEjaXZsI3d2I21pemJwMSNFcHcjcWEjYnBtem0ja2l2I3F2Ym16a21sbSNRdiNQcWEjeHptYW12a20jbXtrbXhiI0lhI3BtI3htenVxYmJtYnBHI1BtI3N2d2VtYnAjRXBpYiMraXh4bWl6bWJwI2J3I1BxYSNrem1pYmN6bWEjSWEsI0ptbnd6bSN3eiNJbmJteiN3eiNKbXBxdmwjYnBtdTEjVnd6I2FwaXR0I2JwbXwja3d1eGlhYSNJY29wYiN3biNwcWEjc3Z3ZXRtbG9tI017a214YiNpYSNQbSNlcXR0bWJwMSNQcWEjYnB6d3ZtI2x3YnAjbXtibXZsI1dkbXojYnBtI3BtaWRtdmEjSXZsI3d2I21pemJwLyNpdmwjUG0jbm1tdG1icCNWdyNuaWJxb2NtI3F2I29jaXpscXZvI0l2bCN4em1hbXpkcXZvI2JwbXUvI053eiNQbSNxYSNicG0jVXdhYiNQcW9wMSNCcG0jQWN4em11bSMrcXYjb3R3enwsMQ==
*/
#include <bits/stdc++.h>

#define F first
#define S second
#define endl '\n'
#define pb push_back

const long long MOD = 1e9 + 7;
const long long SZ = 18;
const long long MAXN = 1e6 + 1;
const int MXN = 2e5 +777;
using namespace std;

typedef long long ll;

long long readInt() {
    bool minus1 = false;
    long long result = 0;
    char ch;
    ch = getchar();
    while (true) {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus1 = true; else result = ch-'0';
    while (true) {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result*10 + (ch - '0');
    }
    if (minus1)          
        return -result;
    else
        return result;
}

int a[MAXN];

set <int> L[MXN]; 

set <int> cnt[MXN];

int lvl[MAXN];
vector <int> g[MAXN];
int up[MAXN][SZ];
int d[MAXN];

int dfs(int v, int par) {
    lvl[v] = lvl[par] + 1;
    up[v][0] = par;
    for (int i = 1; i < SZ; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    d[v] = 1;
    for (auto i : g[v]) {
        if (i == par) continue;
        dfs(i, v);
        d[v] += d[i];
    }
}
int lca(int a, int b) {
    if (lvl[a] > lvl[b]) swap(a, b);
    for (int i = SZ - 1; i >= 0; i--) {
        if (lvl[up[b][i]] >= lvl[a]) {
            b = up[b][i];
        }
    }
    if (a == b) return a;
    for (int i = SZ - 1; i >= 0; i--) {
        if (up[b][i] != up[a][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}

int main() {
	#ifdef IZI_KATKA
	assert(freopen("input", "r", stdin));
    assert(freopen("output", "w", stdout));
    #endif
    int n = readInt(), m = readInt(), q = readInt();
    for (int i = 1; i < n; i ++) {
    	int u = readInt(), v = readInt();
    	g[u].pb(v);
    	g[v].pb(u);
    }
    dfs(1, 0);
	for (int i = 1; i <= m; i++) {
		a[i] =  readInt();
		cnt[a[i]].insert(i);

		if (i != 1) {
			L[lca(a[i], a[i - 1])].insert(i-1);				
		}
	}
    while(q--) {
    	int type = readInt();
    	if (type == 1) {
			int pos = readInt(), v = readInt();
			cnt[a[pos]].erase(pos);
			if (pos != 1) {
				L[lca(a[pos - 1], a[pos])].erase(pos - 1);
			}
			if (pos != n) {
				L[lca(a[pos], a[pos + 1])].erase(pos);
			}
			a[pos] = v;
			cnt[v].insert(pos);
			if (pos != 1) {
			    L[lca(a[pos - 1], a[pos])].insert(pos - 1);
			} 
			if (pos != n) {
				L[lca(a[pos], a[pos + 1])].insert(pos);
			}
    	} else {
    		int l = readInt(), r = readInt(), v = readInt(); 	
        	if (!cnt[v].empty()) {
				int ans = *cnt[v].begin();
				cout << ans << ' ' << ans << endl;
				continue;
			}
			if (!L[v].empty()) {
				int ans = *L[v].begin();
				cout << ans << ' ' << ans + 1 << endl;
				continue;
			} 
			cout << "-1 -1\n";
    	}
    }
    return 0;
}

Compilation message

treearray.cpp: In function 'int dfs(int, int)':
treearray.cpp:64:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
treearray.cpp: In function 'int main()':
treearray.cpp:122:11: warning: unused variable 'l' [-Wunused-variable]
       int l = readInt(), r = readInt(), v = readInt();  
           ^
treearray.cpp:122:26: warning: unused variable 'r' [-Wunused-variable]
       int l = readInt(), r = readInt(), v = readInt();  
                          ^

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 42744 KB Wrong output format.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 42744 KB Wrong output format.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 42744 KB Wrong output format.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 42744 KB Wrong output format.
2 Halted 0 ms 0 KB -