oj.uz

Submission #89618

# Submission time Handle Problem Language Result Execution time Memory
89618 2018-12-17T15:18:36 Z Vardanyan Birthday gift (IZhO18_treearray) C++14
0 / 100
 6 ms 4984 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2*1000*100+5;
int a[N];
vector<int> g[N];
int colour[N];
int par[N];
void kaxel(int v,int p = -1){
    par[v] = p;
    for(int i = 0;i<g[v].size();i++){
        int to = g[v][i];
        if(to == p) continue;
        kaxel(to,v);
    }
}
void dfs(int v,int p,int col){
    colour[v] = col;
    for(int i = 0;i<g[v].size();i++){
        int to = g[v][i];
        if(to == p) continue;
        dfs(to,v,col);
    }
}
int main(){
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i = 1;i<=n-1;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    kaxel(1);

    for(int i = 1;i<=m;i++) scanf("%d",&a[i]);
    while(q--){
        int tp;
        scanf("%d",&tp);
        if(tp == 1){
            int pos,val;
            scanf("%d%d",&pos,&val);
            a[pos] = val;
        }
        else{
            int l,r,v;
            scanf("%d%d%d",&l,&r,&v);
            for(int i = 1;i<=n;i++) colour[i] = 0;
            for(int i = 0;i<g[v].size();i++){
                int to = g[v][i];
                dfs(to,par[to],i+1);
            }
            bool f = false;
            for(int i = l;i<=r;i++){
                if(v == a[i]){
                    printf("%d %d\n",i,i);
                    f = true;
                    break;
                }
                if(i == r) continue;
                if(!colour[a[i]]) continue;
                int col_now = colour[a[i]];
                for(int j = i+1;j<=r;j++){
                    if(!colour[a[j]]) break;
                    if(col_now == colour[a[j]]) continue;
                    printf("%d %d\n",i,j);
                    f = true;
                    break;
                }
                if(f) break;
            }
            if(f) continue;
            printf("-1 -1\n");
        }
    }

    return 0;
}

Compilation message

treearray.cpp: In function 'void kaxel(int, int)':
treearray.cpp:10:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<g[v].size();i++){
                   ~^~~~~~~~~~~~
treearray.cpp: In function 'void dfs(int, int, int)':
treearray.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<g[v].size();i++){
                   ~^~~~~~~~~~~~
treearray.cpp: In function 'int main()':
treearray.cpp:48:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0;i<g[v].size();i++){
                           ~^~~~~~~~~~~~
treearray.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&q);
     ~~~~~^~~~~~~~~~~~~~~~~~~
treearray.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~
treearray.cpp:35:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1;i<=m;i++) scanf("%d",&a[i]);
                             ~~~~~^~~~~~~~~~~~
treearray.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&tp);
         ~~~~~^~~~~~~~~~
treearray.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&pos,&val);
             ~~~~~^~~~~~~~~~~~~~~~~~
treearray.cpp:46:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d%d",&l,&r,&v);
             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB n=5
2 Incorrect 6 ms 4984 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB n=5
2 Incorrect 6 ms 4984 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB n=5
2 Incorrect 6 ms 4984 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB n=5
2 Incorrect 6 ms 4984 KB Wrong range.
3 Halted 0 ms 0 KB -