#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <fstream>
#include <math.h>
using namespace std;
#define vt vector
#define INF 0x3f3f3f3f
#define pb push_back
#define FORR1(n) for(int i = 0; i < n; i++)
#define FORR2(i,n) for(int i = 0; i < n; i++)
#define all(u) u.begin(),u.end()
typedef long long ll;
typedef vt<int> vi;
typedef pair<int,int> pii;
struct CTD{
int size;
vi par;
vt<set<int>> tree;
vi sub;
void init(vt<set<int>> &adj){
size = adj.size();
par.resize(size);
tree=adj;
sub.resize(size);
par[0] = -1;
build(0,-1);
}
void build(int u, int p) {
int n = dfs(u, p); // find the size of each subtree
int centroid = find_centroid(u, p, n); // find the centroid
par[centroid] = p;
// for each tree resulting from the removal of the centroid
set<int> ref = tree[centroid];
for (auto v : ref) {
tree[centroid].erase(v); // remove the edge to disconnect
tree[v].erase(centroid); // the component from the tree
build(v, centroid);
}
}
int dfs(int u, int p) {
sub[u] = 1;
for (auto v : tree[u])
if (v != p) sub[u] += dfs(v, u);
return sub[u];
}
int find_centroid(int node, int p, int n){
for(auto& e: tree[node]){
if(e!=p&&sub[e]>n/2){
return find_centroid(e,node,n);
}
}
return node;
}
};
struct fwtree{
int size;
vi arr;
void init(int n){
size = n;
arr.resize(n+2);
for(int i = 0; i < n+2; i++){
arr[i] = 0;
}
}
void update(int i, int x){
for(; i <= size; i+=i&-i){
arr[i]+=x;
}
}
int get(int i){
int ans = 0;
for(; i > 0; i-=i&-i){
ans+=arr[i];
}
return ans;
}
int get(int l, int r){
return get(r)-get(l-1);
}
};
struct point{
long double x, y;
};
bool operator<(point p1, point p2){
return p2.x>p1.x||(p2.x==p1.x&&p2.y>p1.y);
}
vt<pair<int,int>> adjlist[200005];
vi adj[200005];
void solve(){
int n;
cin>>n;
cin>>n;
string s;
cin>>s;
vi colors(n);
for(int i = 0; i < n; i++){
colors[i] = s[i]-'0';
}
for(int i = 0; i < n; i++){
int j1, j2;
if(i!=n-1){
j1 = i+1;
}else{
j1 = 0;
}
if(i!=0){
j2 = i-1;
}else{
j2 = n-1;
}
adjlist[i].pb({j2,colors[j2]});
adjlist[i].pb({j1,colors[i]});
}
for(int i = 0; i < n-3; i++){
int u,v,c;
cin>>u>>v>>c;u--;v--;
adjlist[u].pb({v,c});
adjlist[v].pb({u,c});
if(v>u)swap(u,v);
adj[u].pb(v);
}
set<int> st;
bool bol1 = true;
for(int i = 0; i < n; i++){
if(st.empty()){
for(auto& e: adj[i]){
st.insert(e);
}
continue;
}
if(*(st.begin())==i){
st.erase(st.begin());
}
for(auto& e: adj[i]){
if(e>*(st.begin())){
bol1 = false;
}else{
st.insert(e);
}
}
}
if(!bol1){
cout<<"neispravna triangulacija";
return;
}
bool bol = true;
for(int i = 0; i < n; i++){
vt<pii> e = adjlist[i];
sort(all(e));
if(e.size()==2){
if(e[0].second==e[1].second){
bol = false;
continue;
}
}
for(int j = 0; j < e.size()-1; j++){
if(e[j].first==(i==0?n-1:i-1)&&e[j+1].first==(i==n-1?0:i+1)){
continue;
}
if(e[j+1].second==e[j].second){
bol = false;
}
}
if(e[0].second==e[e.size()-1].second){
if(!(e[0].first==1&&e[e.size()-1].first==n-1||e[0].first==0&&e[e.size()-1].first==n-2))
bol = false;
}
}
cout<<(bol?"tocno":"neispravno bojenje");
}
int main() {
solve();
return 0;
}
Compilation message
checker.cpp: In function 'void solve()':
checker.cpp:195:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
195 | for(int j = 0; j < e.size()-1; j++){
| ~~^~~~~~~~~~~~
checker.cpp:205:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
205 | if(!(e[0].first==1&&e[e.size()-1].first==n-1||e[0].first==0&&e[e.size()-1].first==n-2))
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
355 ms |
26304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
313 ms |
26188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
