Submission #577075

#	Time	Username	Problem	Language	Result	Execution time	Memory
577075		AGE	Checker (COCI19_checker)	C++14	75 / 110	3073 ms	324148 KiB

checker

#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pb push_back

using namespace std;
const int N=2e6,M=3e3+2,mod=1e9+7;
int seg[N],x[N],y[N],z[N];
vector< pair<int,int> > v[N];
vector<int>adj[N];
vector< pair<int,int> > adjj[N];
map< pair<int,int> , int > col;


void update(int v,int tl,int tr,int index){

    if(tl==tr){

        /*if(seg[v]==0)
            seg2[v]=1;

        else
            seg3[v]=1;*/

        seg[v]=!seg[v];

        return ;

    }

    int tm=(tl+tr)/2;

    if(index<=tm)
        update(v*2,tl,tm,index);

    else
        update(v*2+1,tm+1,tr,index);

    seg[v]=seg[v*2]+seg[v*2+1];
    /*seg2[v]=seg2[v*2]+seg2[v*2+1];
    seg3[v]=seg3[v*2]+seg3[v*2+1];*/


}

int get(int v,int tl,int tr,int l,int r){

    if(tl>r||tr<l)
        return 0;

    if(tl>=l&&tr<=r)
        return seg[v];

    int tm=(tl+tr)/2;

    return get(v*2,tl,tm,l,r)+get(v*2+1,tm+1,tr,l,r);

}
main(){

    int xx;
    cin>>xx;

    if(xx==4||xx==3){

    int n;
    cin>>n;


    string s;
    cin>>s;

    for(int i=1;i<=n;i++){

        if(i==n){

            col[{n,1}]=s[i-1]-'0';
            col[{1,n}]=s[i-1]-'0';
            adj[1].pb(n);
            adj[n].pb(1);

        }

        col[{i,i+1}]=s[i-1]-'0';
        col[{i+1,i}]=s[i-1]-'0';
        adj[i].pb(i+1);
        adj[i+1].pb(i);

    }

    map<int,int>mp;

    for(int i=0;i<n-3;i++){

        cin>>x[i]>>y[i]>>z[i];

        col[{x[i],y[i]}]=z[i];
        col[{y[i],x[i]}]=z[i];
        adj[x[i]].pb(y[i]);
        adj[y[i]].pb(x[i]);

        v[min(x[i],y[i])].pb({1,i+1});
        v[max(x[i],y[i])].pb({0,i+1});

    }


    bool Final_ans=0;

    for(int i=1;i<=n;i++){

        for(auto x:v[i])
            if(x.F==0)
                update(1,1,n,mp[x.S]);

        for(auto x:v[i]){

            if(x.F==1)
                continue;

            int xxx=get(1,1,n,mp[x.S]+1,i);
            if(xxx!=0)
                Final_ans=1;

        }

        for(auto x:v[i]){
            if(x.F==1)
                mp[x.S]=i,update(1,1,n,i);
        }

    }

    bool Final_ans2=0;

    for(int i=0;i<n-3;i++){

        if(adj[x[i]].size()<adj[y[i]].size()){

            for(int j=0;j<adj[x[i]].size();j++){

                if(col[{y[i],adj[x[i]][j]}]==0)
                    continue;

                if(col[{y[i],adj[x[i]][j]}]==col[{x[i],adj[x[i]][j]}]||col[{y[i],adj[x[i]][j]}]==col[{y[i],x[i]}]||col[{x[i],adj[x[i]][j]}]==col[{x[i],y[i]}])
                    Final_ans2=1;

            }

        }

        else{

            for(int j=0;j<adj[y[i]].size();j++){

                if(col[{x[i],adj[y[i]][j]}]==0)
                    continue;


                if(col[{x[i],adj[y[i]][j]}]==col[{y[i],adj[y[i]][j]}]||col[{x[i],adj[y[i]][j]}]==col[{y[i],x[i]}]||col[{y[i],adj[y[i]][j]}]==col[{x[i],y[i]}])
                    Final_ans2=1;

            }

        }

    }

    if(Final_ans==1)
        cout<<"neispravna triangulacija"<<endl;

    else if(Final_ans==0&&Final_ans2==0)
        cout<<"tocno"<<endl;

    else if(Final_ans==0&&Final_ans2==1)
        cout<<"neispravno bojenje"<<endl;

    }

    else{

    int n;
    cin>>n;

    string s;
    cin>>s;
    map< pair<int,int> , pair<int,int> > mp;

    for(int i=1;i<=n;i++){
        if(i==n)
            mp[{n,1}]={1,s[i-1]-'0'},mp[{1,n}]={1,s[i-1]-'0'};
        mp[{i,i+1}]={1,s[i-1]-'0'};
        mp[{i+1,i}]={1,s[i-1]-'0'};
    }


    for(int i=0;i<n-3;i++){

        cin>>x[i]>>y[i]>>z[i];
        adjj[x[i]].pb({y[i],z[i]});
        adjj[y[i]].pb({x[i],z[i]});
        mp[{x[i],y[i]}]={1,z[i]};
        mp[{y[i],x[i]}]={1,z[i]};

    }

    int ok=0;

    for(int i=0;i<n-3;i++){
        for(int j=0;j<n-3;j++){

            if(i==j)
                continue;

            if((min(x[i],y[i])<max(x[j],y[j]))&&(max(x[i],y[i])>max(x[j],y[j]))&&(min(x[i],y[i])>min(x[j],y[j])))
                ok=1;

        }
    }
    int ok2=0;

    for(int i=0;i<n-3;i++){

        for(int j=1;j<=n;j++){

            if(j==x[i]||j==y[i])
                continue;

            pair<int,int> p;
            p={0,0};
            if((mp[{x[i],j}]. F!=0)&&(mp[{y[i],j}].F!=0)){

                if((mp[{x[i],j}].S==mp[{y[i],j}].S)||(mp[{x[i],j}].S==mp[{x[i],y[i]}].S)||(mp[{y[i],j}].S==z[i]))
                    ok2=1;
            }
        }
    }

    if(ok2==0&&ok==0)
        cout<<"tocno"<<endl;

    else if(ok==0&&ok2==1)
        cout<<"neispravno bojenje"<<endl;

    else
        cout<<"neispravna triangulacija"<<endl;



    }
    return 0;

}

Compilation message (stderr)

checker.cpp:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   60 | main(){
      | ^~~~
checker.cpp: In function 'int main()':
checker.cpp:141:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |             for(int j=0;j<adj[x[i]].size();j++){
      |                         ~^~~~~~~~~~~~~~~~~
checker.cpp:155:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |             for(int j=0;j<adj[y[i]].size();j++){
      |                         ~^~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 23 / 23
• Subtask 4: 23 / 23
• Subtask 5: 0 / 35