oj.uz

Submission #577080

# Submission time Handle Problem Language Result Execution time Memory
577080 2022-06-14T03:03:45 Z AGE Checker (COCI19_checker) C++14
110 / 110
 2375 ms 268668 KB 
#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){

        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];

}

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;

    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-1);
            if(xxx!=0)
                Final_ans=1;

        }

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

    }

    for(int i=1;i<=2e6-1;i++)
        seg[i]=0;

    for(int i=n;i>=1;i--){

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

        for(auto x:v[i]){

            if(x.F==0)
                continue;

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

        }


        for(auto x:v[i])
            if(x.F==0)
                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;



    return 0;

}

Compilation message

checker.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main(){
      | ^~~~
checker.cpp: In function 'int main()':
checker.cpp:159: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]
  159 |             for(int j=0;j<adj[x[i]].size();j++){
      |                         ~^~~~~~~~~~~~~~~~~
checker.cpp:173: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]
  173 |             for(int j=0;j<adj[y[i]].size();j++){
      |                         ~^~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 156836 KB Output is correct
2 Correct 70 ms 156888 KB Output is correct
3 Correct 68 ms 156852 KB Output is correct
4 Correct 69 ms 156884 KB Output is correct
5 Correct 71 ms 156800 KB Output is correct
6 Correct 74 ms 156840 KB Output is correct
7 Correct 69 ms 156800 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 156836 KB Output is correct
2 Correct 70 ms 156888 KB Output is correct
3 Correct 68 ms 156852 KB Output is correct
4 Correct 69 ms 156884 KB Output is correct
5 Correct 71 ms 156800 KB Output is correct
6 Correct 74 ms 156840 KB Output is correct
7 Correct 69 ms 156800 KB Output is correct
8 Correct 79 ms 157924 KB Output is correct
9 Correct 80 ms 157920 KB Output is correct
10 Correct 78 ms 157892 KB Output is correct
11 Correct 86 ms 157960 KB Output is correct
12 Correct 79 ms 157912 KB Output is correct
13 Correct 77 ms 157972 KB Output is correct
14 Correct 79 ms 158028 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2365 ms 268448 KB Output is correct
2 Correct 2310 ms 268328 KB Output is correct
3 Correct 2314 ms 268380 KB Output is correct
4 Correct 2341 ms 268308 KB Output is correct
5 Correct 2375 ms 268604 KB Output is correct
6 Correct 2341 ms 251244 KB Output is correct
7 Correct 2163 ms 251036 KB Output is correct
8 Correct 2208 ms 251088 KB Output is correct
9 Correct 2186 ms 251180 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2310 ms 268376 KB Output is correct
2 Correct 2363 ms 268668 KB Output is correct
3 Correct 2276 ms 268420 KB Output is correct
4 Correct 2326 ms 268332 KB Output is correct
5 Correct 2373 ms 268348 KB Output is correct
6 Correct 2151 ms 251252 KB Output is correct
7 Correct 2180 ms 251024 KB Output is correct
8 Correct 2285 ms 250940 KB Output is correct
9 Correct 2137 ms 251056 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 156836 KB Output is correct
2 Correct 70 ms 156888 KB Output is correct
3 Correct 68 ms 156852 KB Output is correct
4 Correct 69 ms 156884 KB Output is correct
5 Correct 71 ms 156800 KB Output is correct
6 Correct 74 ms 156840 KB Output is correct
7 Correct 69 ms 156800 KB Output is correct
8 Correct 79 ms 157924 KB Output is correct
9 Correct 80 ms 157920 KB Output is correct
10 Correct 78 ms 157892 KB Output is correct
11 Correct 86 ms 157960 KB Output is correct
12 Correct 79 ms 157912 KB Output is correct
13 Correct 77 ms 157972 KB Output is correct
14 Correct 79 ms 158028 KB Output is correct
15 Correct 2365 ms 268448 KB Output is correct
16 Correct 2310 ms 268328 KB Output is correct
17 Correct 2314 ms 268380 KB Output is correct
18 Correct 2341 ms 268308 KB Output is correct
19 Correct 2375 ms 268604 KB Output is correct
20 Correct 2341 ms 251244 KB Output is correct
21 Correct 2163 ms 251036 KB Output is correct
22 Correct 2208 ms 251088 KB Output is correct
23 Correct 2186 ms 251180 KB Output is correct
24 Correct 2310 ms 268376 KB Output is correct
25 Correct 2363 ms 268668 KB Output is correct
26 Correct 2276 ms 268420 KB Output is correct
27 Correct 2326 ms 268332 KB Output is correct
28 Correct 2373 ms 268348 KB Output is correct
29 Correct 2151 ms 251252 KB Output is correct
30 Correct 2180 ms 251024 KB Output is correct
31 Correct 2285 ms 250940 KB Output is correct
32 Correct 2137 ms 251056 KB Output is correct
33 Correct 2290 ms 268388 KB Output is correct
34 Correct 2337 ms 268408 KB Output is correct
35 Correct 2295 ms 268408 KB Output is correct
36 Correct 2288 ms 268420 KB Output is correct
37 Correct 2227 ms 268352 KB Output is correct
38 Correct 2277 ms 268204 KB Output is correct
39 Correct 2315 ms 268280 KB Output is correct
40 Correct 2241 ms 251016 KB Output is correct
41 Correct 2176 ms 251032 KB Output is correct
42 Correct 2084 ms 250980 KB Output is correct
43 Correct 2254 ms 251016 KB Output is correct