oj.uz

Submission #797111

# Submission time Handle Problem Language Result Execution time Memory
797111 2023-07-29T06:53:11 Z vjudge1 Making Friends on Joitter is Fun (JOI20_joitter2) C++14
0 / 100
 408 ms 372 KB 
#include<iostream>
#include<vector>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define fi first
#define se second
using namespace std ;
const short NS = 50 ;
short ans ;
bool us[NS + 1][NS + 1] ;
vector<int> v[NS + 1], v1[NS + 1] ;
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    short n, m ;
    cin >> n >> m ;
    if(n <= 50)
    {
        vector<pair<int, int>> pr ;
        while(m--)
        {
            short a, b ;
            cin >> a >> b ;
            if(!us[a][b])
            {
                ans++ ;
                us[a][b] = 1 ;
//                cout << a<<"->"<< b << '\n' ;
                v[a].push_back(b) ;
                v1[b].push_back(a) ;
                if(us[b][a])pr.push_back({a, b}) ;
            }
            bool flag = 1 ;
            while(flag)
            {
                flag = 0 ;
                for(auto i : pr)
                {
                    int y = i.fi, z = i.se ;
                    for(int j : v1[y])
                        if(j != z && !us[j][z])
                        {
                            ans++ ;
                            flag = 1 ;
//                            cout << j<<"->"<< z << '\n' ;
                            v[j].push_back(z) ;
                            v1[z].push_back(j) ;
                            us[j][z] = 1 ;
                            if(us[j][z] && us[z][j])
                                pr.push_back({j, z}) ;
                        }
                    for(int j : v1[z])
                        if(j != y && !us[j][y])
                        {
                            ans++ ;
                            flag = 1 ;
//                            cout << j<<"->"<< y << '\n' ;
                            v[j].push_back(y) ;
                            v1[y].push_back(j) ;
                            us[j][y] = 1 ;
                            if(us[j][y] && us[y][j])
                                pr.push_back({j, y}) ;
                        }
                }
            }
            cout << ans << '\n';
        }
        return 0 ;
    }
    return 0 ;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 408 ms 372 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 408 ms 372 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 408 ms 372 KB Output isn't correct
8 Halted 0 ms 0 KB -