oj.uz

Submission #413250

# Submission time Handle Problem Language Result Execution time Memory
413250 2021-05-28T11:46:45 Z losmi247 Stations (IOI20_stations) C++14
13 / 100
 1168 ms 712 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;

int deg[N];
vector <int> g[N];



vector <int> label(int n,int k,vector <int> u,vector <int> v){
    for(int i = 0; i < n; i++){
        deg[i] = 0;
        g[i].clear();
    }

    for(int i = 0; i < n-1; i++){
        deg[u[i]]++;
        deg[v[i]]++;
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }


    bool prvi = 1;
    for(int i = 0; i < n; i++) if(deg[i] > 2) prvi = 0;
    if(prvi){
        int cnt = 0;
        vector <int> l(n,0);
        queue <pair<int,int>> q;
        for(int i = 0; i < n; i++){
            if(deg[i] == 1){
                q.push({i,-1});
                break;
            }
        }
        while(!q.empty()){
            int u = q.front().first,par = q.front().second;
            l[u] = cnt++;
            q.pop();
            for(auto v : g[u]){
                if(v == par) continue;
                q.push({v,u});
            }
        }
        return l;
    }


    bool drugi = 1;
    for(int i = 0; i < n-1; i++){
        if(u[i] != i+1 || v[i] != i/2) drugi = 0;
    }
    if(drugi){
        vector <int> l(n,0);
        for(int i = 0; i < n; i++) l[i] = i;
        return l;
    }
}

int find_next_station(int s,int t,vector <int> c){
    if((s == 0 && c.size() == 1 && c[0] == 1) || (c.size() == 1 && c[0] == s-1) || (c.size() == 2 && c[0] == s-1 && c[1] == s+1)){
        if(s < t){
            return s+1;
        }
        else{
            return s-1;
        }
    }

    bool drugi = 1;
    for(auto f : c){
        if(f != (s&1 ? s/2 : (s-1)/2) && f != 2*s+1 && f != 2*s+2) drugi = 0;
    }
    if(drugi){
        int nd1 = s,nd2 = t;
        vector <int> putt = {t};
        vector <int> puts = {s};
        while(nd1 != nd2){
            if(nd1 > nd2){ nd1 = (nd1&1 ? nd1/2 : (nd1-1)/2); puts.push_back(nd1); }
            else{ nd2 = (nd2&1 ? nd2/2 : (nd2-1)/2); putt.push_back(nd2); }
        }
        if(nd1 == s){
            return putt[putt.size()-2];
        }
        if(nd1 == t){
            return puts[1];
        }
        return puts[1];
    }
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
   59 | }
      | ^
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:91:1: warning: control reaches end of non-void function [-Wreturn-type]
   91 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 516 KB Output is correct
2 Correct 575 ms 520 KB Output is correct
3 Correct 1097 ms 404 KB Output is correct
4 Correct 827 ms 512 KB Output is correct
5 Correct 718 ms 508 KB Output is correct
6 Correct 553 ms 564 KB Output is correct
7 Correct 501 ms 712 KB Output is correct
8 Correct 3 ms 464 KB Output is correct
9 Correct 8 ms 500 KB Output is correct
10 Correct 2 ms 480 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 528 KB Output is correct
2 Correct 681 ms 528 KB Output is correct
3 Correct 961 ms 492 KB Output is correct
4 Correct 691 ms 644 KB Output is correct
5 Correct 656 ms 516 KB Output is correct
6 Correct 461 ms 504 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 564 KB Output is correct
2 Correct 561 ms 528 KB Output is correct
3 Correct 915 ms 400 KB Output is correct
4 Correct 860 ms 516 KB Output is correct
5 Correct 636 ms 400 KB Output is correct
6 Correct 651 ms 528 KB Output is correct
7 Correct 550 ms 508 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Incorrect 818 ms 400 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1168 ms 492 KB Output is correct
2 Correct 872 ms 400 KB Output is correct
3 Correct 729 ms 528 KB Output is correct
4 Correct 4 ms 464 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Incorrect 725 ms 400 KB Wrong query response.
8 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 597 ms 508 KB Output is correct
2 Correct 532 ms 528 KB Output is correct
3 Correct 1089 ms 400 KB Output is correct
4 Correct 870 ms 400 KB Output is correct
5 Correct 763 ms 508 KB Output is correct
6 Correct 564 ms 528 KB Output is correct
7 Correct 582 ms 512 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 480 ms 528 KB Output is correct
12 Correct 689 ms 584 KB Output is correct
13 Correct 1168 ms 508 KB Output is correct
14 Correct 728 ms 508 KB Output is correct
15 Correct 682 ms 400 KB Output is correct
16 Correct 607 ms 528 KB Output is correct
17 Incorrect 790 ms 516 KB Wrong query response.
18 Halted 0 ms 0 KB -