oj.uz

답안 #1079514

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1079514 2024-08-28T16:17:21 Z anango 기지국 (IOI20_stations) C++17
10 / 100
 659 ms 1192 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define cout cerr


vector<vector<int>> adjlist;

vector<int> depth;
vector<int> tin;
vector<int> tout;
int tim = 0;

void dfs(int node, int par) {
    tin[node] = tim++;
    for (int j:adjlist[node]) {
        if (j!=par) {
            depth[j] = depth[node]+1;
            dfs(j,node);
        }
    }
    tout[node] = tim++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
    adjlist=vector<vector<int>>(n);
    tin=tout=vector<int>(n,-1);
    depth=vector<int>(n,0);
    for (int i=0; i<n-1; i++) {
        adjlist[u[i]].push_back(v[i]);
        adjlist[v[i]].push_back(u[i]);
    }
    dfs(0,-1);
	for (int i = 0; i < n; i++) {
        if (depth[i]%2==1) {
		    labels[i] = tin[i]+1;
        }
        else {
            labels[i] = 1000+tout[i]+1;
        }
        //cout << i << " " << tin[i] <<" " << tout[i] <<" " << labels[i] << endl;
	}

    //consider using the euler tour trick on the tree
    //for each node, store the left and right times of its subtree in the label (using perfect hashing)
    //for a node, you know the tin and tout (call these inv and outv)
    //then for every child, you also know the tin and tout of that child (call these inc and outc)
    //and the tin and tout of the destination (call these ind and outd)
    //so you know that if inv<=ind<=outd<=outv, then the destination is in this subtree
    //and if inc<=ind<=outd<=outc for some child, the destination is in the subtree of this child
    //if none of these hold, then go up
    //this uses at most n^2 labels
    //we could just use in but then it jambloats because we don't know where the subtree ends
    //actually what about storing out for even depth
    //because we know one of the in values for child for free
    //and if we know out[node] we know one out value for free
    //that should work for 2000

	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    sort(c.begin(), c.end());

    //cout << "TRY FIND " << endl;
    for (auto i:c) {
        //cout << i <<" ";
    }
    //cout << endl;
    //cout << "DOING " << s <<" " << t << endl;
    if (t>1000) {
        t-=1000;
    }
    if (s>1000) {
        //depth is even
        s-=1000;
        //so all the children are in-values, our node is an out-value
        //the lowest in-value is actually the parent, so that can be ignored
        c.push_back(s+1);
        sort(c.begin(), c.end());
        assert(*max_element(c.begin(), c.end())==s+1);
        for (int i=2; i<c.size(); i++) {
            if (c[i-1]<=t && t<c[i]) {
                return c[i-1];
            }
        }
        return c[0];
    }
    else {
        //depth is odd
        for (int i=0; i<c.size(); i++) {
            c[i]-=1000;
        }
        //so all the children are out-values, our node is an in-value
        //max value is actually the parent
        c.push_back(s+1);
        sort(c.begin(), c.end());
        //assert(c.front()==s+1);
        ////cout << "DOCTORED C " << endl;
        for (auto i:c) {
            //cout << i <<" ";
        }
        //cout << endl;
        for (int i=1; i<((int)c.size())-1; i++) {
            if (c[i-1]<=t && t<=c[i]) {
                return c[i]+1000;
            }
        }
        return c.back()+1000;
    }
	return c[0];
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:68:15: warning: unused variable 'i' [-Wunused-variable]
   68 |     for (auto i:c) {
      |               ^
stations.cpp:84:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int i=2; i<c.size(); i++) {
      |                       ~^~~~~~~~~
stations.cpp:93:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for (int i=0; i<c.size(); i++) {
      |                       ~^~~~~~~~~
stations.cpp:102:19: warning: unused variable 'i' [-Wunused-variable]
  102 |         for (auto i:c) {
      |                   ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 600 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=1020
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 344 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=2992
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1192 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 623 ms 684 KB Output is correct
2 Correct 456 ms 684 KB Output is correct
3 Correct 456 ms 684 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 444 ms 684 KB Output is correct
8 Correct 659 ms 684 KB Output is correct
9 Correct 450 ms 684 KB Output is correct
10 Correct 405 ms 684 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 2 ms 776 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 1 ms 760 KB Output is correct
15 Correct 0 ms 768 KB Output is correct
16 Correct 346 ms 684 KB Output is correct
17 Correct 346 ms 684 KB Output is correct
18 Correct 386 ms 684 KB Output is correct
19 Correct 383 ms 684 KB Output is correct
20 Correct 382 ms 692 KB Output is correct

Subtask #5
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1192 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -